# If P=NP, are all P problems NP-complete?

In my understanding, if we could prove one of the NP-complete problems is a P problem, then all of the NP problems are P problems. Because P problems are NP problems and NP problems are P problems, P=NP.

I thought if P=NP, then all NP-complete problems are also P problems, but not all P problems are NP-complete.

But it seems that if P=NP, P=NP=NP-complete problems.

I wonder what my blind spot is.

• – D.W.
Jun 12 at 4:40

In order to be NP-complete, the problem has to be also NP-hard. That means, there exists a polynomial-time reduction from SAT to the given problem. The mapping has to map all satisfiable instances of SAT to YES-instances of the problem, and all unsatisfiable instances of SAT to NO-instances of the problem. This means that, any NP-hard problem has to be nontrivial: there should be at least one YES-instance and at least one NO-instance.

On the other hand, if you think about it, that is precisely the sufficient condition to be NP-hard: if your problem has both an YES-instance and a NO-instance, then you can design a simple polynomial-time reduction from SAT: given a SAT-instance $$f$$, decide if $$f$$ is satisfiable or not in polynomial-time (possible since P=NP), and if it is satisfiable, then map it to the YES-instance, and if not, map it to the NO-instance.

So, when P=NP, all P problems are NP-complete, except those trivial problems where all answers are YES, or all answers are NO.

AYun's right. I was confused by the "trivial" instances in P because there is no mapping from SAT to an all-yes problem.

$$NPC\subset NP$$, that's your possible mistake. Do not use equal, because they are not equal at all.