# 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,399 questions
Filter by
Sorted by
Tagged with
15k views

### Is legislation NP-complete?

I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is ...
29k 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 ...
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 ...
14k views

### Why are some games np-complete?

I read the Wikipedia entry about "List of NP-complete problems" and found that games like super mario, pokemon, tetris or candy crush saga are np-complete. How can I imagine np-completeness of a game? ...
6k 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?
29k views

### Are there NP problems, not in P and not NP Complete?

Are there any known problems in $\mathsf{NP}$ (and not in $\mathsf{P}$) that aren't $\mathsf{NP}$ Complete? My understanding is that there are no currently known problems where this is the case, but ...
14k 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 ...
24k 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 ...
10k 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. ...
2k 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 ...
905 views

### Graph problem known to be $NP$-complete only under Cook reduction

The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a ...
2k views

### Longest Repeated (Scattered) Subsequence in a String

Informal Problem Statement: Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right ...
18k 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 ...
10k views

### Rule of thumb to know if a problem could be NP-complete

This question was inspired by a comment on StackOverflow. Apart from knowing NP-complete problems of the Garey Johnson book, and many others; is there a rule of thumb to know if a problem looks like ...
771 views

2k views

### Is 2-SAT with XOR-relations NP-complete?

I'm wondering if there is a polynomial algorithm for "2-SAT with XOR-relations". Both 2-SAT and XOR-SAT are in P, but is its combination? Example Input: 2-SAT part: ...
2k views

### NP-hard problems but only for n≥3

2-SAT is in P; 3-SAT is NP-complete. Exact cover by 2-sets is in P; exact cover by 3-sets is NP-complete Two-dimensional matching is in P; three-dimensional matching is NP-complete Graph 2-coloring is ...
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 ...
7k views

### Prove NP-completeness of deciding satisfiability of monotone boolean formula

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