In my last exam this question got asked and i just cant find a clear answer:

If P=NP, which two languages are NOT NP-complete?

So I assume there are two special languages, but which?

Thanks in advance

  • 1
    $\begingroup$ The language containing no words, and the language containing all words. $\endgroup$ – Yuval Filmus Sep 7 '17 at 14:32
  • $\begingroup$ Thanks, could you elaborate why exactly those two? $\endgroup$ – mind Sep 7 '17 at 14:35
  • 3
    $\begingroup$ It's a good exercise for you. $\endgroup$ – Yuval Filmus Sep 7 '17 at 14:36
  • 1
    $\begingroup$ @mind as Yuval says, take the empty language and try to prove that it is NP-complete. You will pretty quickly reach a dead-end and be enlightened. $\endgroup$ – Pål GD Sep 7 '17 at 16:16

For $L$ to be $NP$-complete, every problem in $NP$ must be reducible to an instance of $L$ in polynomial time. If $P=NP$, you can solve any potential problem in $NP$ directly within polynomial time, and then just branch and output an instance known to be either in or not in $L$ (in constant time), to prove that $L$ is $NP$-complete. However, two languages lack the required pair of instances - the empty language fails to have an instance that accepts, and its complement fails to have an instance that rejects. If at least one problem in $NP$ has some instances that accept and some instances that reject, then you can't reduce it to either of these two languages, and therefore they are not $NP$-complete. To wrap up the proof, you'd need to give an example of such a problem and the instances, which should be fairly trivial.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.