Are all NP problems also NP-complete?

Question

The definition of NP-complete is

A problem is NP-complete if

1. it belongs to class NP
2. all the other problems in NP polynomially transform to it

So, if all other problems in NP transform to an NP-complete problem, then does that not also mean that all NP problems are also NP-complete? What is the point of classifying the two if they are the same?

In other words, if we have an NP problem then through (2) this problem can transform into an NP-complete problem. Therefore, the NP problem is now NP-complete, and NP = NP-complete. Both classes are equivalent.

Just trying to clarify this up for myself.

Answer 1

Are all NP problems also NP-complete?

Only if P = NP.

Answer 2

Not necessarily. It can happen that NP is a known upper-bound (ie. we know how to solve it in non-deterministic polynomial time) but not a known lower-bound (a more efficient algorithm may or may not exist).

An example of such a problem is graph isomorphism.

Your sentence "if we have an NP problem then [...] this problem can transform into an NP-complete problem" is incorrect for the simple following reason: any problem in P is also in NP, yet no problem in P is NP-complete (unless P=NP, of course).