Are all NP problems also NP
The definition of NP-complete is
A problem is NP-complete if
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.
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).
Are all NP problems also NP-complete?
Only if P = NP.
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 .
上一篇: 完成与NP
下一篇: 所有的NP问题都是NP吗？