# How do we distinguish NP-complete problems from other NP problems?

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

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

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.

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