0
$\begingroup$

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.

Thanks in advance!

$\endgroup$
1

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

Here is original Answer:

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

$\endgroup$
2
  • $\begingroup$ picture I think this picture means if p=np, then p=np=np-complete? $\endgroup$
    – AL-CEL
    Jun 9 at 3:21
  • $\begingroup$ I've understood my mistakes, you can check AYun's answer. Sorry for my wrong. $\endgroup$
    – LighT
    Jun 9 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.