Lets assume $P = NP$. Can we say if every language $L \in P$, then $L \in NPC$?

I read $P \subseteq NP$, which means that $L\in NP$. So I know for example, that a language can be $NP \text{ hard}$, but it doesn't have to be in $NP$, e.g. $HALT$.

But what about the case above. Is the language also $NPC$?

  • $\begingroup$ A diagram. $\endgroup$ – Karolis Juodelė Dec 27 '13 at 18:44
  • $\begingroup$ @KarolisJuodelė: Could you also explain it with a few sentences? I saw the same diagram on wikipedia, but I could not find an explanation for it. $\endgroup$ – tumbler Dec 27 '13 at 18:59
  • $\begingroup$ This question is answered in the Wikipedia article on NP-completeness; see the diagram on the upper-right. I have higher expectations for the amount of research you do on your own before asking. $\endgroup$ – D.W. Mar 7 '14 at 19:11

Yes. Every* problem in $P$ can be reduced to any other problem in $P$ using polynomial-time reductions (since the reduction is allowed to do polynomial work, it can just solve the problem itself).

If $P=NP$, then it follows that every* problem in $NP$ can be reduced to any* other problem in $NP$ -- in other words, every* problem in $NP$ is $NP$-complete. This implies that if $L \in P$ and if $P=NP$ then* $L$ is $NP$-complete.

Footnote *: There is an exception for the empty language ($\emptyset$) and the universal language ($\Sigma^*$). For purposes of gaining a rough conceptual understanding, this technical detail can probably be safely ignored.

  • $\begingroup$ Hi D.W., I have a question to a statement of yours. You said:" If $P=NP$, then it follows that every problem in NP can be reduced to any other problem in NP..." What about if $P!=NP$. Does it still follow that every Problem in $NP$ can be reduced to any other problem in $NP$? $\endgroup$ – tumbler Dec 31 '13 at 14:40
  • $\begingroup$ @user2965601, no, if $P\neq NP$, then there are problems in $NP$ and not in $P$ that are not $NP$-complete. $\endgroup$ – Luke Mathieson Feb 15 '14 at 5:06

Yes, the language will be in $NPC$ because $NPC \subseteq NP$.

  • 2
    $\begingroup$ The "Yes" is correct but the "because" is not a good explanation of why. (How do we know $NPC$ isn't a proper subset of $NP$? It's not, but how do we know that? Your answer doesn't explain why not.) $\endgroup$ – D.W. Dec 28 '13 at 0:20

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.