# Questions tagged [np-complete]

Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

1,412 questions
Filter by
Sorted by
Tagged with
20 views

### Proof that there isn't a $c$-additive approximation to Partition Problem

Define Partition to consist of all tuples $x_1,\ldots,x_n$ which can be divided to two groups in which the sums of the two groups are equal. Is there a proof that there isn't an additive approximation ...
24 views

### Polynomial reduction to SAT with a condition

Let L be in NP. Is there always a reduction from L to SAT where atleast m-1 clauses (m being the number of clauses in the CNF formula) can be satisfied? When w is in L it is trivial because the ...
9k views

### Are there subexponential-time algorithms for NP-complete problems?

Are there NP-complete problems which have proven subexponential-time algorithms? I am asking for the general case inputs, I am not talking about tractable special cases here. By sub-exponential, I ...
25 views

### Minimum number of intervals to cover all possible colors

Given $n$ points in $\mathbb{R}$ each colored with one of following three colors $$C=\{c_1, c_2, c_3\}.$$ In polynomial time, Choose the minimum number of intervals of length $1$ each containing some ...
77 views

### Can we DISPROVE that a problem is NP-complete

So I basically had an exam question in which we were given a problem and we had to prove or disprove that it was in NP-complete. I tried to prove it but could not because apparently it could not be ...
29 views

### Difficulty in finding a counter example for a polynomial reduction

I am doing some exercises on proving NP Complete problems and the first problem was directed bipartite graphs with a Hamiltonian cycle and the second one was undirected bipartite graphs with a ...
24 views

### How to reduce 3-SAT to Set Splitting

I've been reading through Garey & Johnson's "Computers and intractability", and a problem SP4 caught my attention. It is stated as following: Given a collection $C$ of subsets of a ...
45 views

### Is $\Pi’\propto_{poly}\Pi$ for any two NP-complete problems $\Pi,\Pi'$?

I am facing the following question: Let $\Pi$ and $\Pi$’ be two NP-complete problems, prove or refute $\Pi’\propto_{poly}\Pi$. I do not understand the meaning of this question and how to answer it. ...
20 views

19 views

### Reduction from SAT to EXACTSAT

PROBLEM: EXACTSAT INPUT: A boolean formula $\phi$ in CNF with $n$ variables, and a natural number $k \le n$. OUTPUT: "Yes" if and only if there is truth assignment $\theta$ which sets ...
89 views

### Proving that a class equals NP ∩ coNP

We say that a non-deterministic Turing machine is nice if for every input x the following holds: • Every computation path returns either ’accept’, ’reject’ or ’quit’. • There is at least one non-quit ...
9k views

### What is practical difference between NP and PSPACE-complete?

Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing. Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$\,\neq\,$NP, ...
99 views

### Approximation factor preserving reduction

The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365: Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving ...
27 views

### Is integer multicommodity flow problem is NP-hard?

As Wikipedia states the time complexity of Integer Linear programming(ILP) is NP-hard, so this means integer multicommodity flow problem is also NP-hard?
39 views

### chromatic number is np-hard

I'm referring to a question in this book: Algorithms by Jeff Erickson, link:http://jeffe.cs.illinois.edu/teaching/algorithms/notes/J-approx.pdf, in particular, pg.21, Q11. The author mentioned that ...
87 views

### P-NP related 3 sub-problems

This is a question on a practice final. Which of the following statements are true? If it is false, what is the underlying reason behind that? I. If 3-CNF-SAT is in P, then Clique is also in P. II. ...
90 views

### Optimization problem with discrete and continuous components

Suppose we have a sequence of $m$ tokens $(T_1, T_2, \ldots, T_m)$. We can split this sequence considering two parameters $w$ (which is the width of the window) and $x$ which is the overlap between ...
32 views

28 views

### Prove that T3SAT is NP-Complete

Instance: A boolean formula f(x1, . . . , xn) in 3CNF form, with m clauses labelled C1, . . . , Cm. Is there an assignment to x1, . . . , xn such that every third clause is False and all other clauses ...
33 views

### A be an NP-complete problem, and if B be an NP-hard problem. If A is polynomial time solvable then is B is polynomial time solvable?

if A be an NP-complete problem, and if B be an NP-hard problem. If A is polynomial time solvable then is B is polynomial time solvable? on the contrary, if A be an NP-complete problem, and B be an NP-...
22 views

### Is this variant of Subset Product NP-hard? [duplicate]

Given a set $Y$ with whole number positive divisors of $N$, is there a combination of divisors that have a product equal to $N$? Does Subset Product remain NP-hard when whole number divisors are only ...
743 views

### How exactly is the process of showing a problem to be NP-Complete a proof by contradiction?

The steps involved in proving that a problem is NP-Complete are fairly straightforward to follow, it's the logic behind why the proof is valid that's really throwing me for a loop. Okay so an easy one:...
61 views

### Complexity of still life extentions in Game of Life

The game of life is one of the most famous cellular automata in 2D. It has a variety of objects, some of them are moving like gliders, some have an oscillating behavior and others do not change at all,...
297 views

### Circuit satisfiability problem : SAT-C to SAT-2C

I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C. Prove that ...
41 views

### Variant of "Exact Cover by 3-Set "

Exact cover by 3-sets is 𝖭𝖯-complete: Instance: Given a finite set $X = \{x_1, x_2, …, x_{3n}\}$ of $3n$ elements and a collection $C = \{(x_{i_1}, x_{i_2}, x_{i_3})\}$ of 3-elements subsets of $X$; ...
32 views

### Independent Feedback Vertex Set

In Independent Feedback Vertex Set, we are given an undirected graph $G$, and an integer $k \in \mathbb{N}$. The objective is to decide whether there exists a feedback vertex set S of G of size at ...
31 views

### Why proofs of Cook's Theorem assume k is given (n^k for NTM)?

A typical proof of Cook-Levin's Theorem proceeds like this: Suppose problem X is in NP. Then there is an NTM M deciding X in time n^k, for some k. Given a word w, NTM M, and k, we construct a Boolean ...
146 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 }...
29 views

### Is Knapsack-optimization problem NP-hard while Knapsack-search problem NP-complete?

I am learning Computational Complexity. Is Knapsack-optimization problem (find an arrangement to maximize the value) known to be NP-hard, while Knapsack-search problem (find an arrangement so that ...
47 views

### Are there any FNP-complete problems with a unique solution?

Are there any FNP-complete problems where there's only one possible solution? For example, the travelling salesman problem can have multiple routes all shorter than $X$. There's only one shortest ...
13 views

### Need Help Solve an NP problem with an Approximation Algorithm

I have an algorithm problem which I do not know how to solve and I think it is NP-complete. Let me try to explain with a general example. Given $n$ objects, each with $k$ possible properties, ...
36 views

### NP-Completeness of SAT with given hamming weight k [duplicate]

I think that the following problem is NP-Complete but I don't have any idea of how doing the reduction. Input: A propositional formula $\varphi$ and a number $k$. Output: Yes if exists an valuation \$\...
210 views

### Why the Cook-Levin reduction is not a parsimonious reduction?

In the textbook Arora-Barak, after presenting the Cook-Levin theorem's proof the authors say that the proof can be modified slightly to make the reduction parsimonious. The parsimonious reduction is ...