# 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 cs.stackexchange.com/questions/2655/… – Zat Mack Jul 9 '12 at 15:35
It may be worth noting that if P $=$ NP, then NP-complete and NP are the same. So there may be no way to distinguish them. – Jason DeVito Jul 9 '12 at 15:50
Apparently we can't easily show that a problem $p \in \mathsf{ NP} \backslash \mathsf{ NPC}$. See the question on MO: Qiaochu Yuan (mathoverflow.net/users/290), What techniques exist to show that a problem is not NP-complete?, mathoverflow.net/questions/9221 (version: 2009-12-18) – user2468 Jul 9 '12 at 16:22

As @Jason DeVito mentioned, this is impossible if $P=NP$. If $P\neq NP$, then one way to distinguish would be to produce two NP problems, A & B, such that there is no polynomial time reduction of B to A. Then B is not NP-complete. One trivial way to do this is to let B be a trivial problem, like determining membership in the emptyset. This is clearly in NP, but cannot poly-time compute any NP-complete problem. The point here is that the class NP is closed downward.