4
$\begingroup$

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

  • 2
    Apparently we can't easily show that a problem [$p \in \mathsf{ NP} \backslash \mathsf{ NPC}$](http://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg). See the question on MO: Qiaochu Yuan (mathoverflow.net/users/290), What techniques exist to show that a problem is not NP-complete?, http://mathoverflow.net/questions/9221 (version: 2009-12-18)2012-07-09

1 Answers 1

0

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.