Questions tagged [polynomial-time-reductions]

Used in questions asking for efficient (polynomial-time) reductions between computational problems.

Filter by
Sorted by
Tagged with
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 ...