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

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

• The language containing no words, and the language containing all words. – Yuval Filmus Sep 7 '17 at 14:32
• Thanks, could you elaborate why exactly those two? – mind Sep 7 '17 at 14:35
• It's a good exercise for you. – Yuval Filmus Sep 7 '17 at 14:36
• @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. – Pål GD Sep 7 '17 at 16:16

## 1 Answer

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.