Questions tagged [polynomial-time-reductions]
Used in questions asking for efficient (polynomial-time) reductions between computational problems.
50
questions
0
votes
1answer
27 views
Polynomial time reducibility is an equivalence relation
How do I prove the following statement?
The relation $≤_p$ (polynomial time reduction) is an equivalence relation.
-1
votes
1answer
43 views
If A is not in NP, and A reduces to B, does this mean B is not in NP?
I know it is true that if A is not in P, and A reduces B, then B is not in P.
But is it true for NP as well?
If A is not in NP, and A reduces to B, does this mean B is not in NP?
Why or why not?
...
0
votes
1answer
34 views
Reduce Subset-Sum to Sat
Is there a reduction from SUBSET-SUM to SAT?
Just general SAT, not 3-SAT.
Also the given multiset S only has positive integers.
SUBSET-SUM is defined as follows:
Input: a multiset S = { x1 , ... , xn }...
4
votes
1answer
31 views
Complexity of a decision problem: system of linear equations over finite field with restricted solutions
I have a system of linear equations over a finite field $\mathbb F_p \cong \mathbb Z_p$, and I'm interested in the decision problem of whether there exists a solution where all of the variables $x_i$ ...
0
votes
0answers
28 views
Reduction from cardinality constrained project selection problem to CLIQUE problem
Give the polynomial-time $A$ algorithm of the cardinality constrained project selection problem plus the integer k, we are able to compute a maximum-profit set of at most projects to undertake, can we ...
0
votes
0answers
21 views
Reducing the Hamiltonian Cycle problem to the problem of finding a $m$-length Hamiltonian Cycle
I was working through some exercises regarding NP complexity, when I came across this one:
Let $mH$ be the problem of finding a Hamiltonian cycle of length $m$ ($m$ fixed) in a graph $G$. A cycle of ...
0
votes
0answers
22 views
How to prove the complexity of this modified version of the minimum dominating set problem?
I have an optimization problem and I want to show its complexity. The optimization problem is the same as the minimum dominating set problem, but with an additional constraint. The constraint is easy. ...
1
vote
1answer
55 views
What is the polynomial time reduction between these two Hamiltonian cycle problems?
Problem 1: Given an undirected graph, return the edges of a Hamiltonian cycle, or correctly decide that the graph has no such cycle.
Problem 2: Given an undirected graph, decide whether or not the ...
1
vote
1answer
23 views
Reduction from VC to {a,k | a is a 3DNF (disjunctive normal form) and there exists an assignment satisfying exactly k clauses in a}
I have the following question :
\begin{align}
L_2 = \{a,k\ \mid \text{ a is a 3DNF (disjunctive normal form) and} \\
\text{there exists an assignment $z$ satisfying exactly $k$ clauses in }a\}
\end{...
2
votes
2answers
429 views
Definition of NP-hardness for non-decision problems
As I understand, the term "NP-hardness" is applicable when we also talk about optimization or search problems (i.e. return the satisfying assignment for 3-SAT). How do we formally define NP-...
1
vote
1answer
40 views
Converting a Mixed SUBSET-SUM Problem To All-Positive Case
Let's say we have a SUBSET-SUM problem with list {$x_1,x_2,x_3,...x_N$} and weight $W$, with some of $x_i<0$. Is there a known way, in polynomial time, to convert this problem into an equivalent ...
2
votes
1answer
238 views
SAT satisfaction with 10 variables
I am trying to prove that the next problem is NPC:
$$
A = \{ \langle\phi\rangle \ \big| \ \phi \ \text{is CNF and has sat. assignment where exactly 10 vars are TRUE} \}
$$
I am trying to find ...
0
votes
0answers
35 views
$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$
I want to prove that $$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$$. Does anyone have a Idea how to solve this ?
0
votes
2answers
70 views
Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle
The following is an excerpt from a material on NP-Theory:
"Let G be an undirected graph and let s and t be vertices in G. A Hamiltonian path in G is a
path from s to t using edges of G, on which ...
0
votes
0answers
22 views
planar 1-in-3 sat described as a planar graph for independent set
Given a planar 1-in-3 sat formula, can someone reduce that formula into a graph that asks the question when ever there is an independent set for it, that's also planar?
1
vote
1answer
93 views
Is Monotone 3-SAT with exactly 3 distinct variables untractable?
I have given the following SAT variation:
Given a formula F in CNF where each clause C has exactly 3 distinct literals and for each C in F either all literals are positive or all literals are negated....
0
votes
0answers
11 views
Does $L \leq_p K$ and $K\in NP$ implies $L \in NP$?
I only find theorems like $L \leq_p K$ and $K\in P$ implies $L \in P$ in books, but I think the same should be true for NP as well. Or is there anything I am missing?
I am asking since this would be ...
2
votes
0answers
29 views
Multipoint evaluation of a given polynomial
You are given a polynomial of degree n. We have to find the value of the polynomial at n different points in O(n(log(n))^2). The answer should be modulo 998244353.
I have read various blogs on it and ...
1
vote
0answers
52 views
Finding $l$ subsets such that their intersection has less or equal than $k$ elements NP-complete or in P?
I have a set $M$, subsets $L_1,...,L_m$ and natural numbers $k,l\leq m$.
The problem is:
Are there $l$ unique indices $1\leq i_1,...,i_l\leq m$, such that
$\hspace{5cm}\left|\bigcap_{j=1}^{l} L_{i_{j}}...
1
vote
1answer
77 views
Polynomial-Time reduction from Partition to MakeSpan
Partition Problem:
Input: $A:=$ {$a_{1}, ..., a_{n} $}. $a_{i} \in \mathbb{N}$ $\forall i \in$ $\{1, \ldots, n\}$.
Question: Exists a subset $A_{1} \subset A$ with: $\sum_{a_{i} \in A_{1}} a_{i} = \...
0
votes
1answer
38 views
Reducing 3-coloring problem to trio representatives
A group of students is divided into trios - groups of 3 members. Each student can be assigned to more than more trio. We want to assign their representatives, by choosing exactly one member of each ...
-1
votes
1answer
81 views
Close To Cook Reduction given NP != coNP
I am struggling to answer these two questions:
Prove or wrong:
Both are given the assumption that NP != coNP.
For any 2 decision problems S, S', if there is a Cook reduction from S' to S then there ...
3
votes
2answers
148 views
Solving Exact2IS using IS
i encountered the following problem:
Exact2IS ={G has exactly 2 independent sets}
Assuming that given a graph G i can find an independent set how can i check if G has exactly 2 independent sets.
(i ...
4
votes
1answer
178 views
Prove finding k disjoint paths from n given paths in a directed graph is NP-complete
Problem: Given n paths in a directed graph G(V, E) and an integer k, find out k paths among them such that no two of them pass through a common node.
Prove that the given problem is in NP-complete.
...
0
votes
0answers
20 views
Consequences if Exact Cover had a reduction that allowed it to be solved in pseudo-polynomial time?
Here's a pretend example.
$S$ = $[9,4,7]$
$C$ = $[[9,4],[7]]$
$f(x)$ = magically encode $x ∈ S$, then $C$ so that the $total~sum~S$ has a value that is $n$^$1000$
Because the value is bounded by ...
0
votes
1answer
24 views
Will this reduction of Exact Cover into Subset-Sum fail due to a potential false positive?
After removing multi-sets and sets that have elements that don't exist in $S$.
$S$ = $[9,6,7,4,5,1,8]$
$C$ =$[[9,6,7],[4,5],[1,8]]$
Transform the values in $C$ of the shared index values with $S$. ...
1
vote
1answer
56 views
Karp reduction from optimization problems to decision problems
When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other.
Focusing on Cook reductions, there exists a natural Karp ...
1
vote
1answer
37 views
Solving subgraph isomorphism in polynomial time
So I am a bit confused about the reduction between SAT, subgraph isomorphism (SI) and graph isomorphism (GI).
I know that GI is in NP, and that SI is NP-complete.
So I'm thinking if we can decide ...
1
vote
1answer
73 views
Is there a language that cannot be polynomially reduced to?
Is there a language A that cannot be polynomially reduced to by some language B? Or is it always possible to reduce a language B to A?
0
votes
2answers
222 views
Reducing Vertex Cover to Half Vertex Cover
I need to reduce Vertex Cover to Half Vertex Cover using a Karp reduction:
Vertex Cover: Given a graph $G = (V,E)$ and an integer $k$, is there a subset of $V$ of size $k$ which intersects all edges?
...
0
votes
0answers
36 views
Validity of a simple polynomial-time reduction [duplicate]
Let say that P is an NP-hard optimization problem and Q is a problem with unknown complexity. Additionally, we have an algorithm for solving problem Q. We can solve problem P with input x in the ...
0
votes
1answer
51 views
A non-polynomial reduction
Given two problems $P_1$ and $P_2$. $P_1$ is NP-complete in the strong sense and we want to prove that $P_2$ is also NP-complete but the reduction from $P_1$ to $P_2$ is not polynomial. Can we say ...
0
votes
0answers
27 views
Find decidable sets such that $A$ reduces to $B$ but not vice versa
I am stuck in this problem, so any help is appreciated. The problem asks to show that there exists decidable sets $A$ and $B$ such that $A \leq_{m}^{p} B$ but $B \not \leq_{m}^{p} A$, and that $A$, $B$...
0
votes
1answer
90 views
Restriction of SAT to CNF
I have spent a lot of time understanding these two issues. If you can help me, please.
Prove that the restriction of SAT to CNF formulas in which each variable xi appears at most twice is solvable in ...
5
votes
1answer
60 views
Is there such a notion as “effectively computable reductions” or would this be not useful
Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by ...
1
vote
1answer
44 views
polynomial reduction & co np complete
I would like to know how we can demonstrate these two problems :
$A \leqslant_p B$ implies $\overline A \leqslant_p \overline B$
The complement of 3-SAT is co-NP-complete
2
votes
0answers
32 views
A polynomial time reduction and the size of problem (exact cover)
An exact cover problem is one of the NP-complete problems.
Given a family $\mathbb{I}$ of subsets of a set $[n]=\{1,\dotsc,n\}$, whether there exists a subfamily $\mathbb{I}'\subseteq \mathbb{I}$ ...
0
votes
0answers
22 views
Good NP-complete reduction candidates for disjoint bilinear programs
Given a disjoint bilinear programm $max\{x^TQy: x \in X, y\in Y\}$, with $Q$ being a matrix and $X$ and $Y$ specific polytops (i.e. like X = knapsack polytop or Y = stable set polytop)
What are some ...
0
votes
0answers
65 views
If any problem in NP is not in P then NP C ∩ P = ∅
If any problem in NP is not in P then NPC ∩ P = ∅
The proof is: We have $X ∈ NP$ and $X \not\in P$. Assume $Y ∈ NP C ∩ P$. As $X ≤_P Y$ we have $X ∈ P$, which is a contradiction.
I have not clear ...
0
votes
1answer
1k views
Reduction from Vertex Cover to Dominating Set
I am trying to reduce the vertex cover (decision) problem to the dominating set (decision) problem in order to prove that the latter is NP-hard. After some research online, I found that many articles ...
1
vote
0answers
36 views
What are the requirements for a superset of P to be closed under karp reductions?
So today in our exercise session on complexity theory we discussed that P, NP, and BPP are closed under karp reduction. We also figured that the proofs could likely be expanded to straight ...
1
vote
1answer
30 views
If $Q$ reduces to $L$ then $\overline{Q}$ reduces to $\overline{L}$
The following exercise is taken from Chapter 17 of Languages and Machines by Thomas Sudkamp:
Let $Q$ be a language reducible to a language $L$ in polynomial time. Prove that $\overline{Q}$ is ...
1
vote
1answer
196 views
Concrete example of Vertex Cover to Subset Sum reduction
In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem, mostly to prove Subset Sum is NP-Complete. I also see a reduction in the line ...
1
vote
2answers
346 views
P/NP - Polynomial Reduction vs Certificate
I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate.
How I understand polynomial reduction is that you can use it to ...
3
votes
1answer
43 views
Why can KARP reductions be used to define completeness for complexity classes in the polynomial hierachy?
When defining $\Sigma_i^P$ or $\Pi_i^P$ completeness, we want to use a reduction that fulfills the following property:
If $L' \leq_p L$ and $L \in \Sigma_i^P$ or $\Pi_i^P$ respectively, then $L'$ is ...
0
votes
1answer
87 views
Are every problems in EXP karp reducible to any EXP-Complete?
According to wikipedia and other references there exists complete language $L \in EXP$ such that for every languages $L'$ in $EXP$ there exists a polynomial reduction $f$ that converts instance of $L'$...
2
votes
1answer
115 views
CLIQUE $\leq_p$ SAT
i'm trying to reduce CLIQUE to SAT:
Given: Graph G=(Vertices V, Edges E) and $k \in \mathbb{N}$
Output: Formular F such that if G contains a complete subgraph of size k, the formular is satisfiable (...
0
votes
1answer
111 views
weighted-clique to vertex cover reduction
WEIGHTED-CLIQUE
input: a undirected graph G that has weighted edges and 2 natural numbers a, b
question: does G have a clique of size a with total weight of b?
I want to prove that this ...
5
votes
1answer
993 views
vertex cover reduction to subset sum
Subset sum
Input: A multi set $S$ of numbers and a natural number $t$
Question: Does $S$ contain a subset $A$ such that $\sum_{x \in A} x =
t$? (e.g., $\{1,1,2,3,4,5\}$, by multiset it ...
2
votes
0answers
55 views
NP-completeness of Induced disjoint paths between a set of sources and a set of sinks
In a given undirected graph $G(V,E)$, a set of $k$ paths is said to be induced if:
They are vertex-disjoint.
Each one is itself an induced path.
No edge connects two vertices of two different paths.
...
