Can it be determined if language L lies in NP?

Question

Given a language L defined by a Turing Machine that decides it, is it possible to determine algorithmically whether L lies in NP?

Answer 1

No. First, by Rice's Theorem, this is a property of TMs that depends only on the language they compute, so it cannot be computable.

But, more than that, it is known that the index set of $NP$ (that is, the set of TMs that compute languages in $NP$) is $\Sigma^0_3$-complete ($\Sigma^0_3$ in the arithmetic hierarchy of computability, not the polynomial hierarchy).

Questions like this were first investigated by Hajek. For more, see e.g. this article by Ken Regan.

A few more great nuggets from Hajek's paper:

• The index set of $P$ is $\Sigma^0_3$-complete.
• $\{i : P^{L(M_i)} \neq NP^{L(M_i)}\}$ is $\Pi^0_2$-complete
• There is a total Turing machine (halts on all inputs) $M_i$ such that $P^{L_i} = NP^{L_i}$ but the statement "$P^{L_i} = NP^{L_i}$" is independent (where $L_i = L(M_i)$). Similarly for relativizations where $P \neq NP$.

Answer 2

The answer to your literal question is no, as Joshua Grochow pointed out.

However, as Holger stated, it is possible to check in linear time whether the nondeterministic Turing machine (NTM) "clocks itself" and halts after n^k steps for some constant k, through some standard way of simulating a clock (such as the code below). Often when a paper or book will suggest (incorrectly) that it is possible to determine if a NTM is polynomial time, this is what they really mean. Perhaps this is why you asked the question? (I had the same question when I first learned complexity theory and somewhere saw the statement that it is possible to check if a TM is poly-time.) The real question is why one might wish to do this, which I discuss below after explaining how.

There are lots ways to add such a clock feature. For instance, imagine on input x of length n, alternately executing one statement of the "primary algorithm" being clocked, and then one statement of the following algorithm, which finishes in (something close to) n^k steps:

for i_1 = 1 to n
  for i_2 = 1 to n
...
        for i_k = 1 to n
          no-op;
return;

If the above code returns before the primary algorithm halts, then halt the entire computation (say, with rejection).

The algorithm that decides if a NTM is of this form, if interpreted as an attempt at an algorithm to decide whether its input is a poly-time NTM, will report some false negatives: some NTMs are guaranteed to halt in polynomial time, even though they do not alternate executing one statement of an algorithm with one statement of a clock like the code above (hence would be rejected despite being poly-time).

But there are no false positives. If a NTM passes the test, then it definitely halts in polynomial time, hence it defines some NP language. However, perhaps the behavior of its underlying primary algorithm is altered, if the clock sometimes runs out before the primary algorithm halts, causing the computation to reject even though the primary algorithm may have accepted if given enough time to finish. Therefore the language decided may be different than that of the primary algorithm. But, and this is key, if the primary algorithm being executed is in fact a polynomial-time algorithm running in time p(n), and if the constant k in the clock is large enough that n^k > p(n), then the primary algorithm will always halt before the clock runs out. In this case, the answer of the primary algorithm is not altered, so the primary algorithm and clocked NTM simulating it therefore decide the same NP language.

Why is this important? This means that it is possible to "enumerate all the NP languages" (which as I said is in the literature often inaccurate stated as "decide whether a given NTM is poly-time" or "enumerate all the poly-time NTM's"). More precisely, it is possible to enumerate an infinite list of NTM's M_1 M_2, ..., with the properties that

1. Each M_k runs in polynomial time (for instance, by attaching a n^k-time clock to M_k), hence decides some NP language, and
2. Each NP language is the language decided by some M_i in the list.

What does not happen is that every polynomial-time NTM is on the list. But each NP language has an infinite number of NTM's representing it. Thus, each NP language is guaranteed to have at least some of its representative NTM's on the list, specifically all those NTM's at a large enough index k that n^k exceeds the running time of M_k.

This is useful for doing tricks like diagonalization, which require algorithmically enumerating such infinite (or unbounded) lists of all NP languages. And of course, this whole discussion applies to many other kinds of machines besides poly-time NTMs, such as poly-time deterministic TMs.

Answer 3

I want to remark that the answer is yes if you consider the input to be a clocked Turing machine, i.e., there is a clock that lets the Turing machine perform $p(n)$ steps and then accepts/rejects. Now checking whether the language decided by the machine is in NP is a syntactic property that boils down to deciding whether the machine is a well-formed nondeterministic Turing machine with a polynomial clock.