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


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.

  • $\begingroup$ The empty set and it's complement are not NP-complete (under Turing or mapping reductions). $\endgroup$ – Tyson Williams Jul 10 '12 at 3:10
  • $\begingroup$ @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. $\endgroup$ – Steven Stadnicki Jul 10 '12 at 16:51
  • $\begingroup$ Yes, I only meant (poly time) mapping reductions. They are NP-complete for (poly time) Turing reductions iff P = NP. $\endgroup$ – Tyson Williams Jul 10 '12 at 21:48
  • $\begingroup$ In short and visually on this image (via this blog). $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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