# 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. Dec 27, 2013 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, 2013 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, 2014 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$?
• @user2965601, no, if $P\neq NP$, then there are problems in $NP$ and not in $P$ that are not $NP$-complete. Feb 15, 2014 at 5:06