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

106 Views Asked by At

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

There are 1 best solutions below

0
On

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.