HiveBrain v1.2.0
Get Started
← Back to all entries
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}$?

Submitted by: @import:stackexchange-cs··
0
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!

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.

Context

StackExchange Computer Science Q#3103, answer score: 9

Revisions (0)

No revisions yet.