3
$\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
3
$\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
  • $\begingroup$ Hmm, I have an understanding in terms of problems, just not in terms of languages. Most lecture notes do not talk about P, NP, and NPC in terms of languages. Thanks, will take another look at P, NP, NPC in terms of languages. $\endgroup$ – LazerSharks Dec 11 '14 at 8:26
  • $\begingroup$ Problems and languages are the same thing. See cs.stackexchange.com/questions/13669/…. $\endgroup$ – Yuval Filmus Dec 11 '14 at 8:31

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