# How to show that the set of machines which accept languages in $\mathrm{NP}\smallsetminus\mathrm P$, is decidable only if $\mathrm P=\mathrm{NP}$?

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!

## 1 Answer

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.