# P vs NP: Assuming P = NP

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$?

• A diagram. – Karolis Juodelė Dec 27 '13 at 18:44
• @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. – user11941 Dec 27 '13 at 18:59
• 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. – 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.
• 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$? – user11941 Dec 31 '13 at 14:40
• @user2965601, no, if $P\neq NP$, then there are problems in $NP$ and not in $P$ that are not $NP$-complete. – Luke Mathieson Feb 15 '14 at 5:06
Yes, the language will be in $NPC$ because $NPC \subseteq NP$.
• 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.) – D.W. Dec 28 '13 at 0:20