15
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Retagged to complexity theory. Not sure what this has got to do with NP-Completeness. $\endgroup$ – Aryabhata Aug 17 '10 at 16:15
  • 1
    $\begingroup$ FWIW, despite votes on the proposal site, I think this question is more on-scope than the one on factoring precisely because the question about factoring would be covered in most intro complexity courses, but this one is not even covered in many graduate-level complexity courses. $\endgroup$ – Joshua Grochow Aug 17 '10 at 16:15
  • 1
    $\begingroup$ Isn't this covered in intro courses on computability as a typical application of Rice's theorem? $\endgroup$ – Moritz Aug 17 '10 at 16:21
  • 3
    $\begingroup$ Moritz - although the yes/no answer to this question is covered by Rice's Theorem, see my answer below for more interesting results. Maybe, txwikinger, you should change the question to "What is the complexity of the set {i : L(M_i) is in NP}?"? $\endgroup$ – Joshua Grochow Aug 17 '10 at 16:28
  • $\begingroup$ I'll second Joshua's answer here. The answer may be obvious when the language is specified by a Turing Machine, but the answer is the same (and perhaps not quite so apparent) if we allow the language to be specified in some arbitrary format. $\endgroup$ – Anand Kulkarni Aug 20 '10 at 2:00
24
$\begingroup$

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$.
$\endgroup$
  • 1
    $\begingroup$ Here the question seems to be a promise decision problem (the given language is promised to be decided by a TM, not only recognized) as opposed to a total decision problem. Will Rice's Theorem still be applicable here then? Recall that the proof of Rice's Theorem employs the undecidability of halting, so undecidability is essential there. $\endgroup$ – Zeyu Aug 17 '10 at 16:44
  • 2
    $\begingroup$ In the question asked the language L was "given by a machine that decides it." So it was really: given a Turing machine M, can it be determined if L(M) is in NP. If the language L were not specified by a TM, but merely given as a subset of the natural numbers, what would it mean to decide algorithmically if L is in NP? In particular, how can we think of L as being input to an algorithm when L itself is not given by a finite description? $\endgroup$ – Joshua Grochow Aug 17 '10 at 16:54
  • 1
    $\begingroup$ Yes I know. But in Rice's Theorem it is possible that the TM does not decide a language, i.e., it does not compute a total function. $\endgroup$ – Zeyu Aug 17 '10 at 17:01
  • 2
    $\begingroup$ It is a general heuristic that, given a semantic property of Turing machines, such as "M defines an NP language", one should first try to express this property in first-order logic. This places the property in a level of the Arithmetic Hierarchy; the heuristic is that the property is usually complete for that level of the hierarchy. I would like to ask whether there are any notable counterexamples to this heuristic. $\endgroup$ – Andy Drucker Aug 17 '10 at 22:33
  • 2
    $\begingroup$ Scaling down to the Polynomial Hierarchy, things are less likely to behave so nicely. For example, consider the property "C is a Boolean circuit of minimal size (for the function it computes)". This problem is NP-hard and can be placed in the Polynomial Hierarchy, but it's open whether it's complete for the level where it naturally resides. (such results are known for some restricted classes of circuits, e.g. DNFs; see the 2-part survey "Completeness in the Polynomial Hierarchy" by Schaefer and Umans.) $\endgroup$ – Andy Drucker Aug 17 '10 at 22:33
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ That only works if it's a clocked nondeterministic TM. If I just give you a clocked TM (even one that runs in exponential time), it's still undecidable whether or not the language it decides is in NP. However, if N_1, N_2, ... is an enumeration of TMs with exponential clocks, the set {i : L(N_i) is in NP} is probably no longer Sigma_3-complete, since you're already guaranteed that the N_i are total, but it's still certainly not computable. $\endgroup$ – Joshua Grochow Aug 18 '10 at 14:45

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.