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
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
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.