Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I just learned that when we have a polynomial algorithm for NP-complete problems, it is possible to use that algorithm to solve all NP problems.

So, the question is how we then distinguish non-NP-complete NP problems from NP-complete problems? It seems that all these problems will have a polynomial algorithm to convert into other problems...

share|improve this question
cross-posted to math.SE –  Zat Mack Jul 9 '12 at 15:36
See also this question on Mathoverflow. –  sdcvvc Jul 9 '12 at 16:16
A highly related question Showing that a problem in X is not X-complete. –  Juho Jul 9 '12 at 17:19
Any course or book teaching what you have learned should have answered your question immediately after. –  Raphael Jul 17 '12 at 13:43

2 Answers 2

up vote 4 down vote accepted

To provide the flip side of 042's answer: it's important to understand that if $P=NP$ then every problem in $NP$ is $NP$-complete (caveat: under the usual poly-time reductions): $NP$-complete simply means 'every problem within $NP$ can be solved in polynomial time with an oracle for this problem'. But if every problem in $NP$ can be solved in polynomial time—that is, if $P=NP$—then the second part of that statement is vacuous.

On the other hand, if $P\neq NP$ then it's known that the problems that are in $NP$ but not in $P$ have a very rich structure - in particular, there have to be 'intermediate' problems that aren't in $P$ but also aren't $NP$-complete, and in fact an infinite number of distinct ones (that is, such that at least one can't be reduced to the other). For more details on this result (Ladner's Theorem), you might start with Lance Fortnow's notes on the topic.

share|improve this answer
The empty set and it's complement are not NP-complete (under Turing or mapping reductions). –  Tyson Williams Jul 10 '12 at 3:10
@TysonWilliams Not under mapping reductions, which is a good point to make, but certainly under Turing reductions in the sense that a polynomial-time Turing machine with an oracle for the empty set can solve any problem in NP. –  Steven Stadnicki Jul 10 '12 at 16:51
Yes, I only meant (poly time) mapping reductions. They are NP-complete for (poly time) Turing reductions iff P = NP. –  Tyson Williams Jul 10 '12 at 21:48
In short and visually on this image (via this blog). –  Raphael Jul 17 '12 at 13:45

Not really. For instance, the Graph isomorphism problem is believed not to be in P, but on the other hand not being NP-complete (and is obviously in NP). Moreover, also all problems in P (that are also in NP) are not NP-complete, if $P \neq NP$. However, to my knowledge, all of these are mere conjectures, since the answer would solve P vs. NP.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.