Questions tagged [polynomial-time-reductions]
Used in questions asking for efficient (polynomial-time) reductions between computational problems.
57
questions
1
vote
0answers
36 views
+50
Reduction between Parity-SAT and approximate counting
Consider two problems as defined here.
Approximate counting: Given a Boolean function $f(x)$, for $x \in \{0, 1\}^{n}$, distinguish between the two cases:
The number of satisfying assignments for $f(...
0
votes
1answer
25 views
If a language consists of an NP and coNP question, do we have to place it in P^NP^NP?
If $x \in L$ only if $x \in A$ and $x \in B$, where A is an NP problem and B is a coNP problem, I cannot place $L \in NP$ or $L \in coNP$ without implying that NP = coNP right?
1
vote
1answer
30 views
Reduction for the proof that COMBI $:= \{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\}$ is NP complete
Given the Language $COMBI := \{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\}$. Proof that Combi is NP-complete.
I tried to reduce Clique <=p Combi. I had two different ...
2
votes
1answer
30 views
$k$-SAT completeness proof when $k$ is linear in number of variables
I'm looking at a special version of SAT in which each clause has exactly $n/2$ literals, where $n$ is the number of variables. Can we prove NP-completeness of SAT in this case?
I tried reducing 3-SAT ...
4
votes
0answers
75 views
Is there any polytime reduction from feedback vertex set to vertex cover?
I know that feedback vertex set (FVS) problem is $\mathrm{NP}$-complete since there is a simple and nice polytime reduction from vertex cover (VC) problem to FVS.
Specifically, given a undirected ...
9
votes
2answers
272 views
NP-hardness for one-dimensional facility location problem with entrance fee for each customer
We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
1
vote
0answers
17 views
Time-Sensitive Reductions for Undecidable Problems
I'm studying Comparability and Complexity, and through the course, a number of problems (namely, the halting problem for Turing Machines, etc.) have been proven undecidable through elementary proofs ...
0
votes
1answer
59 views
How to prove that the subset sum problem is polynomially reducible to the knapsack problem
I want to prove that the subset sum problem is polynomially reducible to the Knapsack problem. Overall I want to show that Knapsack is NP-complete.
There are two parts to showing knapsack is NP-...
0
votes
1answer
130 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
51 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
46 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
34 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
30 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
67 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
24 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
440 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
41 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
241 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
95 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
23 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
110 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
17 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
31 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
53 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
104 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
46 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
89 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 ...
2
votes
2answers
151 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
209 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
61 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
46 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
94 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
254 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
63 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
93 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
64 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
52 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
35 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
69 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
49 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
34 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
249 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 ...
