1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ A diagram. $\endgroup$ 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
5
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Feb 15 '14 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy