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$ – user11941 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.

| cite | improve this answer | |
  • $\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$ – user11941 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$.

| cite | improve this answer | |
  • 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