1
$\begingroup$

Title says it all, but to clarify:

Define a problem, called $IsInNP$, as follows:

Given a Turing Machine $M$ that always halts, $IsInNP$ is the problem of deciding if the problem that $M$ recognizes is in $NP$.

What is the complexity class of $IsInNP$? Is it even decidable? Is the answer the same for any other complexity class, like $NP$-hard? And are those questions even sensible to ask?

By the way, I am aware that the class $NP$ is not enumerable, but since I do not quite understand enumerability and it seems that recursively enumerable problems can be decidable, I do not know if that means that deciding whether a problem is in $NP$, or any other complexity class, is decidable.

Also, I am aware of Rice's Theorem, and I believe it can be interpreted as saying that deciding whether a problem is in $NP$ is undecidable, but I am not certain.

Bonus question if the above questions are sensible: given a property $S$ that only $NP$ problems possess, does the above also mean that deciding whether a problem decided by a Turing Machine $M_2$ has property $S$ is in the same complexity class as $IsInNP$?

$\endgroup$
  • $\begingroup$ You said "the problem that $M$ decides", do you mean "the problem that $M$ recognizes"? If no, since you cannot determine whether $M$ always halts, do you mean the input is guaranteed to be a halting machine? $\endgroup$ – xskxzr Sep 3 at 4:04
  • $\begingroup$ I don't understand what you mean by "a property $S$ that only NP problems possess". Usually we express a property in the context of Rice's theorem as a set of languages, so can you express $S$ as a set of languages? $\endgroup$ – xskxzr Sep 3 at 4:08
  • $\begingroup$ If a machien does not decide any problem (for instance, because on some inputs it runs forever), is it supposed to be in IsInNP? $\endgroup$ – Andrej Bauer Sep 3 at 7:39
  • $\begingroup$ Your problem is either trivially solvable or undecidable, depending on how you define it (what happens when $M$ is not a decider). For this reason it is not so interesting. $\endgroup$ – Yuval Filmus Sep 3 at 8:15
  • $\begingroup$ @xskxzr I meant "the problem that $M$ recognizes". I apologize. $\endgroup$ – Gavin Howard Sep 3 at 18:27
3
$\begingroup$

Here are several interpretations of your question:

$L_1$ consists of all descriptions of Turing machines which are deciders (always halt) and the language that they decide is in NP.

This is undecidable, by reduction from the halting problem. Given a Turing machine $T$, construct a new Turing machine $M$ which erased its input and transfers control to $T$. Then $\langle M \rangle \in L_1$ iff $T$ halts on the empty input.

Indeed, if $T$ halts then $L(M) = \Sigma^*$, while if $T$ doesn't halt, then $M$ is not a decider.

$L_2$ consists of all descriptions of Turing machines which are either not deciders, or the language that they decide is in NP.

This is undecidable, by reduction from the halting problem. Given a Turing machine $T$, construct a new Turing machine $M$ which simulates $T$ on the empty tape, and if $T$ halts, solves some NEXP-complete problem on the original input. Then $\langle M \rangle \in L_2$ iff $T$ doesn't halt on the empty input.

Indeed, if $T$ halts on the empty input then $M$ decides an NEXP-complete problem, which by the nondeterministic time hierarchy theorem doesn't belong to NP. In contrast, if $T$ doesn't halt on the empty input, then $M$ is not a decider.

$L_3$ is the promise problem in which the input is a description of a Turing machine which is promised to be a decider, and the goal is to determine whether the language it decides is in NP.

Alternatively, you can ask whether there exists any decidable language $L_4$ such that

  1. The description of any machine deciding a language in NP belongs to $L_4$.
  2. The description of any machine deciding a language not in NP doesn't belong to $L_4$.

This is undecidable, in the sense that there is no Turing machine that halts and answers YES on all YES instances, and halts and answers NO on all NO instances.

Given a Turing machine $T$, construct a new Turing machine $M$ with two inputs $n,x$. The Turing machine simulates $T$ for $n$ steps. If $T$ halts within these $n$ steps, then it solves some NEXP-complete problem on $x$. Otherwise, it simply returns YES. The new machine $M$ is a YES instance of $L_3$ iff $T$ doesn't halt on the empty input.

Indeed, if $T$ halts on the empty input then there exists an NEXP-complete language $L$ and an integer $n$ such that $(n,x) \in L(M)$ iff $x \in L$, and so $L(M) \notin \mathsf{NP}$. In contrast, if $T$ doesn't halt on the empty input then $L(M)$ consists of all pairs $(n,x)$, and so $L(M) \in \mathsf{NP}$.

$\endgroup$
  • 1
    $\begingroup$ I appreciate that you answered all interpretations of my question; I learned much more because of that. I also learned that I need to be much more precise. $\endgroup$ – Gavin Howard Sep 3 at 18:44

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.