Are all NP problems also NP-complete?

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.

---

Are all NP problems also NP-complete?

Only if P = NP.

---

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

---

If problem A polynomially transforms to problem B, that does not necessarily mean that problem B polynomially transforms to problem A. A problem can only be reduced to a problem of equal or greater difficulty.

If problem C is in NP, but is not NP-complete, then it can be polynomially transformed into any NP-complete problem, but that is not enough to make it NP-complete, because it does not imply that all the other problems in NP polynomially transform to problem C.

---

At least it should be possible to show that a number of NP complete problems are also in P. Take for example the problem of sieving odd prime numbers from from composite odd numbers in a set of odd numbers. It is possible to derive a method in P of doing it. The verification method can also be in P as is discussed in the link below.

https://www.academia.edu/s/bcb7736e1e/proof-of-the-p-verses-np-problem-part-two?source=link

Take the Goldbach conjecture problem, It can be shown to NP complete, the primes adding up to an even number greater than 2 can be obtained in linear time. Each Goldbach number has its own Characteristic line with Goldbach points as points with prime coordinates that add up to the Golbach number. See the link below for more information:

https://www.academia.edu/35904487/Proof_of_the_P_verses_NP_problem-part_one

---

I just want to point out the figure showing P=NP=NPC(if P=NP) in the other answer is wrong. There are 2 cases: empty language ϵ and its complement ∑∗ in P can never be NPC. Because if these two are in NPC, we cannot map any language in P/NP with yes instance to ϵ and map any language in P/NP with no instance to ∑∗, which contradicts the definition of NPC: any NP can be reduced to NPC.