snippetMinor
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}$?
Viewed 0 times
showthemathrmlanguagesacceptdecidablesmallsetminusthatmachineshow
Problem
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!
$$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!
Solution
There are two cases to consider.
-
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.
-
Assume that $\text{P}\neq\text{NP}$. Now your result follows directly from Rice's theorem.
-
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.
-
Assume that $\text{P}\neq\text{NP}$. Now your result follows directly from Rice's theorem.
Context
StackExchange Computer Science Q#3103, answer score: 9
Revisions (0)
No revisions yet.