8
$\begingroup$

I'd like your help with proving that the language $$L=\{\langle M \rangle \mathrel| L(M) \in \mathrm{NP}\smallsetminus \mathrm{P} \}$$ is decidable iff $\mathrm{P}=\mathrm{NP}$.

If $\mathrm{P}=\mathrm{NP}$, I get that it's the language of empty Turing machines. So $L$ is a $\text{co-RE}$ problem — but that's not what's being asked, so I got confused.

I know that in order to show $\mathrm{P}=\mathrm{NP}$, I need to show problem which it's $\mathrm{NPC}$ and $\mathrm{P}$ as well.

Any help? Thanks!

$\endgroup$
9
$\begingroup$

There are two cases to consider.

  1. Assume that $\text{P=NP}$. Then $L=\{\langle M\rangle \mid L(M)\in \emptyset\}=\emptyset$. The empty language is decidable; as no word belongs to it, it is trivial to decide whether a word belongs to it or not.

  2. Assume that $\text{P}\neq\text{NP}$. Now your result follows directly from Rice's theorem.

$\endgroup$

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.