Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# 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.

157 questions
Filter by
Sorted by
Tagged with
4k views

### Dealing with intractability: NP-complete problems

Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?
7k views

### How do I construct reductions between problems to prove a problem is NP-complete?

I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How ...
7k 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 ...
6k views

### “NP-complete” optimization problems

I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems. In an algorithms class, I had the large parsimony problem described as NP-complete. ...
3k views

### Can one show NP-hardness by Turing reductions?

In the paper Complexity of the Frobenius Problem by Ramírez-Alfonsín, a problem was proved to be NP-complete using Turing reductions. Is that possible? How exactly? I thought this was only possible by ...
4k views

### Find a 3-colouring using the 3-colourability decision problem

I was learning about NP problems. I read that for many problems, like Clique, we can easily convert its decision problem to derive a solution of search problem. (For Clique problem, you only need to ...
5k views

### If P = NP, why wouldn't $\emptyset$ and $\Sigma^*$ be NP-complete?

Apparently, if ${\sf P}={\sf NP}$, all languages in ${\sf P}$ except for $\emptyset$ and $\Sigma^*$ would be ${\sf NP}$-complete. Why these two languages in particular? Can't we reduce any other ...
21k views

### Knapsack problem — NP-complete despite dynamic programming solution?

Knapsack problems are easily solved by dynamic programming. Dynamic programming runs in polynomial time; that is why we do it, right? I have read it is actually an NP-complete problem, though, which ...
5k views

### Teaching NP-completeness - Turing reductions vs Karp reductions

I'm interested in the question of how best to teach NP-completeness to computer science majors. In particular, should we teach it using Karp reductions or using Turing reductions? I feel that the ...
35k views

### How can I reduce Subset Sum to Partition?

Maybe this is quite simple but I have some trouble to get this reduction. I want to reduce Subset Sum to Partition but at this time I don't see the relation! Is it possible to reduce this problem ...
14k views

### Is the k-clique problem NP-complete?

In this Wikipedia article about the Clique problem in graph theory it states in the beginning that the problem of finding a clique of size K, in a graph G is NP-complete: Cliques have also been ...
I am trying to solve this problem and I am really struggling. A monotone boolean formula is a formula in propositional logic where all the literals are positive. For example, $\qquad (x_1 \lor x_2) ... 1answer 1k views ### Is regex golf NP-Complete? As seen in this recent XKCD strip and this recent blog post from Peter Norvig (and a Slashdot story featuring the latter), "regex golf" (which might better be called the regular expression separation ... 1answer 353 views ### If a problem is Cook-NP hard, and this problem is in NP, does it prove that the problem is Karp-NP-complete? I got recently confused when I noticed that there exists 2 types of polytime reductions, which lead to 2 different concepts of NP-hardness. This is well explained in the answer to this question: Can ... 1answer 137 views ### If a language is X-complete, is its complement is X-complete as well? I'm looking for an information about closure of complexity complete classes. Is it true that any language, if the language is X-complete, then its complement is X-complete? Why? I was thinking ... 4answers 20k views ### How can I verify a solution to Travelling Salesman Problem in polynomial time? So, TSP (Travelling salesman problem) decision problem is NP complete. But I do not understand how I can verify that a given solution to TSP is in fact optimal in polynomial time, given that there is ... 2answers 3k views ### Types of reductions and associated definitions of hardness Let A be reducible to B, i.e.,$A \leq B$. Hence, the Turing machine accepting$A$has access to an oracle for$B$. Let the Turing machine accepting$A$be$M_{A}$and the oracle for$B$be$O_{B}$. ... 2answers 1k views ### A polynomial reduction from any NP-complete problem to bounded PCP Text books everywhere assume that the Bounded Post Correspondence Problem is NP-complete (no more than$N$indexes allowed with repetitions). However, nowhere is one shown a simple (as in, something ... 2answers 3k views ### Reducing the integer factorization problem to an NP-Complete problem I'm struggling to understand the relationship between NP-Intermediate and NP-Complete. I know that if P != NP based on Ladner's Theorem there exists a class of languages in NP but not in P or in NP-... 1answer 23k views ### Why is the clique problem NP-complete? [duplicate] Possible Duplicate: Is the k-clique problem NP-complete? I've been lately reading about the clique problem, specifically, the variety of the clique problem of deciding whether a given graph$G$... 2answers 459 views ### Modeling the problem of finding all stable sets of an argumentation framework as SAT As a continuation of my previous question i will try to explain my problem and how i am trying to convert my algorithm to a problem that can be expressed in a CNF form. Problem: Find all stable sets ... 4answers 937 views ### Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded? Does the difficulty of a strongly NP-hard or NP-complete problem (as e.g. defined here) change when its input is unary instead of binary encoded? What difference does it make if the input of a ... 2answers 3k views ### How is the Subset Sum Problem NP-Complete? You can't find a solution online for it that doesn't run in polynomial time complexity, when using dynamic programming. Have all these sites secretly solved P=NP, and no one knows about it? 2answers 1k views ### Reduce Vertex Cover with size k to Vertex Cover with size n/2 Disclaimer: This is a homework question. I would like to reduce vertex cover problem to the following problem: $$L = \{G \mid G\text{ has a vertex cover of size } |V(G)|/2\}\,.$$ I have divided the ... 3answers 2k views ### Why is the class NP-Complete important compared to NP-hard? I'm studying computational complexity and I was wondering why the NP-Complete (NPC) problems is an important class at all. I find it obvious why we're interested in showing a given NP problem is NP-... 2answers 755 views ### Why doesn't Godel's Second Incompleteness Theorem rule out a formalizable proof of P!=NP? I'm sure there must be something wrong with the following reasoning because otherwise a lot of P vs. NP research would be curtailed but I cannot determine my error: For any fixed integer$k>0$... 2answers 1k views ### Can we construct a Karp reduction from a Cook reduction between NP problems? We have had several questions about the relation of Cook and Karp reductions. It's clear that Cook reductions (polynomial-time Turing reductions) do not define the same notion of NP-completeness as ... 1answer 524 views ### Finding optimal sequence of questions to minimize total student time Suppose there is a tutorial session at a university. We have a set of$k$questions$Q = \{ q_1 \ldots q_k \}$and a set of$n$students$S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a ... 1answer 3k views ### Negative numbers in Subset-Sum If I have a set$A$with positive and negative numbers, and a number to find C. It is possible to reduce the problem to one with only positive numbers in set$A$? I mean, it is possible to find a ... 3answers 2k views ### Is there an efficient test for if an NFA accepts a subset of another NFA? So, I know that testing if a regular language$R$is a subset of regular language$S$is decidable, since we can convert them both to DFAs, compute$R \cap \bar{S}$, and then test if this language is ... 2answers 7k views ### 3-sat to 2-sat reduction It is known that 3-SAT belong to - NP-Complete complexity problems, while 2-SAT belong to P as there is known polynomial solution to it. So you can state that there is no such reduction from 3-SAT to ... 2answers 1k views ### Why does Schaefer's theorem not prove that P=NP? This is probably a stupid question, but I just don't understand. In another question they came up with Schaefer's dichotomy theorem. To me it looks like it proves that every CSP problem is either in P ... 2answers 7k views ### Relationship between Independent Set and Vertex Cover Directly from Wikipedia, a set of vertices$X \subseteq V(G)$of a graph$G$is independent if and only if its complement$V(G) \setminus X$is a vertex cover. Does this imply that the complement of ... 1answer 4k views ### Do any decision problems exist outside NP and NP-Hard? This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard. In order to be in NP, problems have to have a ... 1answer 3k views ### 3-SAT for variables appearing 3 times I've been trying to investigate 3-SAT for variables appearing 3 times and so far I'm getting some mixed answers as to its complexity. For example, https://people.maths.ox.ac.uk/scott/Papers/... 1answer 2k views ### Why do Shaefer's and Mahaney's Theorems not imply P = NP? I'm sure someone has thought about this before or immediately dismissed it, but why does Schaefer's dichotomy theory along with Mahaney's theorem on sparse sets not imply P = NP ? Here's my ... 1answer 540 views ### NP-complete decision problems - how close can we come to a solution? After we prove that a certain optimization problem is NP-hard, the natural next step is to look for a polynomial algorithm that comes close to the optimal solution - preferrably with a constant ... 1answer 9k views ### Proving NP Completeness of a subset-sum problem - how? So I'm trying to understand P/NPC problems. The one I'm trying to tackle now is subset sum (we have a collection of integers$S$and a$k$param: is there a subset of$S$that sum of all it's elements ... 2answers 805 views ### 3-SAT where variables occur equally many times as a positive literal and as a negative literal Let$\phi$be a 3-CNF formula over variables$x_1,x_2,\ldots,x_n$. Every variable$x_i$,$i \in [n]$, occurs equally many times as a positive literal and as a negative literal in$\phi$. Is it NP-... 0answers 509 views ### 2 Dimensional Subset Sum: looking for information I do not know if this problems exists with a different name, if it is, I could not find it. The problem is this: Given a set$S$of$n$points in$\mathbb{Z}^2$, is there a subset$A\subset S$... 3answers 2k views ### Can't understand why the DP Subset Sum algorithm is not polynomial I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial. Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the ... 1answer 533 views ### When is splitting a collection coins two ways NP-complete? Suppose we have a set$D$of denominations of coins and a our input is a "tip jar" containing some finite number of these coins (e.g., five nickels, a dime and three quarters). In the first two ... 1answer 5k views ### If P = NP, why does P = NP = NP-Complete? [duplicate] If P = NP, why does P = NP also then equal NP-Complete? I.e. Why would it then be the case that ... 1answer 113 views ### Questions on Graph and Hamiltonian [closed] From this book and other study in complexity theory, I have seen the following statement: The definition of NP is not symmetric with respect to yes-instances and no-instances. For example, it is ... 2answers 421 views ### Proving that finding wheel subgraphs is NP-complete Can you help me with this problem ? Given an undirected graph$G$and an integer$n$, prove that determining whether the graph has wheel on$n$vertices$W_{n}$(a wheel$W_{i}$is such that$i$... 1answer 735 views ### Reduction from PARTITION to 3PARTITION I'm considering the problem (a variant of 3-PARTITION, see here) with description Instance: Set of positive integers$A={w_{1},...,w_{n}}$with$S(A)=\sum\limits_{i=1}^{n}w_{i} = 3m$. ... 1answer 959 views ### Reducing from Hamiltonian Cycle problem to the Graph Wheel problem [duplicate] EDIT: This question is different from the other in a sense that unlike it this one goes into specifics and is intended to solve the problem. In the previous post, the only answer was a hint. In this ... 1answer 602 views ### NP-completeness of graph isomorphism through edge contractions with an edge validity condition Given Graphs$G=(V_1,E_1)$and$H=(V_2,E_2)$. Can a graph isomorphic to$H$be obtained from$G$by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset ... 2answers 99 views ### Karp hardness of searching for a matching cut Follow-up question in the series: Karp hardness of searching for a matching erosion Karp hardness of searching for a matching split Maximum Matching Cut problem Input: An undirected graph$G(...
First, read the previous question: Karp hardness of searching for a matching cut As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the ...