4
$\begingroup$

If P = NP, why does P = NP also then equal NP-Complete?

I.e. Why would it then be the case that P = NP = NP-Complete?

Assuming P != NP , there were problems in NP not in NP - Complete. When P = NP, all NP problems are actually now P.

Shouldn't there still be P = NP problems not in NP - Complete?

enter image description here

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ This is a rather simple exercise; use the definitions! To check your work, find the answer here. $\endgroup$ – Raphael♦ Dec 11 '14 at 7:45
4
$\begingroup$

If $P=NP$ then every non-trivial language $L$ is NP-hard, where non-trivial means that $L$ is neither the empty language nor the language of all words. This follows immediately from the definition of NP-hardness (exercise!). In particular, every non-trivial language in NP is NP-hard, and so NP equals NPC plus the two trivial languages.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hmm, I'm sorry, I haven't learned about languages in relation to complexity classes... do you have a short explanation of how are they related? (Good readings you could point me to?) $\endgroup$ – LazerSharks Dec 11 '14 at 7:56
  • $\begingroup$ @Gnuey If you don't know what P, NP and NPC are, you can't expect to understand why P=NP implies P=NP=NPC. So your first step should be to understand the definitions of P, NP and NPC. These are very standard notions, described in many online lecture notes and offline textbooks. Some of these probably even explain why P=NP implies P=NP=NPC. $\endgroup$ – Yuval Filmus Dec 11 '14 at 7:59
  • 1
    $\begingroup$ It follows immediately from the definition of P. It would be pointless for me to spell it out. Either you “get it”, or seeing the proof will only help so much. $\endgroup$ – Yuval Filmus May 16 at 14:37
  • 1
    $\begingroup$ It’s very easy. $\endgroup$ – Yuval Filmus May 16 at 14:40
  • 1
    $\begingroup$ Yes, that’s the idea. $\endgroup$ – Yuval Filmus May 16 at 14:54

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