Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
cross-posted to cs.stackexchange.com/questions/2655/… –  Zat Mack Jul 9 '12 at 15:35
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. –  Jason DeVito Jul 9 '12 at 15:50
2  
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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