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

  • 1
    cross-posted to http://cs.stackexchange.com/questions/2655/how-do-we-distinguish-np-complete-problems-from-other-np-problems2012-07-09
  • 3
    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.2012-07-09
  • 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