Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$?
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.
