<p>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.</p>

<p>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 <em>arithmetic</em> hierarchy of computability, not the polynomial hierarchy).</p>

<p>Questions like this were first investigated by <a href="http://dx.doi.org.proxy.uchicago.edu/10.1016/0304-3975(79)90046-X">Hajek</a>.  For more, see e.g. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.8927&amp;rep=rep1&amp;type=ps">this article</a> by Ken Regan.</p>

<p>A few more great nuggets from Hajek's paper:</p>

<ul>
<li>The index set of $P$ is $\Sigma^0_3$-complete.</li>
<li>$\{i : P^{L(M_i)} \neq NP^{L(M_i)}\}$ is $\Pi^0_2$-complete</li>
<li>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$.</li>
</ul>

CC BY-SA 2.5
2010-08-17T16:44:25.843Z
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.
Zeyu
CC BY-SA 2.5
2010-08-17T16:54:42.337Z
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?
Joshua Grochow
CC BY-SA 2.5
2010-08-17T17:01:20.267Z
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.
Zeyu
CC BY-SA 2.5
2010-08-17T22:33:12.360Z
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.
Andy Drucker
CC BY-SA 2.5
2010-08-17T22:33:31.767Z
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.)
Andy Drucker
CC BY-SA 2.5
2010-08-17T16:16:12.237Z
2010-08-27T22:04:07.393Z
2010-08-27T22:04:07.393Z
Joshua Grochow
<p>The answer to your literal question is no, as Joshua Grochow pointed out.</p>

<p>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 <em>why</em> one might wish to do this, which I discuss below after explaining <em>how</em>.</p>

<p>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:</p>

<pre>
for i_1 = 1 to n
  for i_2 = 1 to n
...
        for i_k = 1 to n
          no-op;
return;
</pre>

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

<p>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).</p>

<p>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.  <b>But</b>, 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.</p>

<p>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</p>

<ol>
<li> 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
<li> Each NP language is the language decided by some M_i in the list.
</ol>

<p>What does not happen is that <em>every</em> 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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-08-20T02:25:46.840Z
2010-08-20T15:19:56.930Z
2010-08-20T15:19:56.930Z
Dave Doty
<p>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.</p>

CC BY-SA 2.5
2010-08-18T14:45:21.993Z
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.
Joshua Grochow
CC BY-SA 2.5
2010-08-18T11:05:11.473Z
2010-08-18T11:05:11.473Z
Holger
<p>Given a language L defined by a Turing Machine that decides it, is it possible to determine algorithmically whether L lies in NP?</p>

CC BY-SA 2.5
2010-08-20T02:00:07.010Z
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.
Anand Kulkarni
CC BY-SA 2.5
2010-08-17T16:15:25.323Z
Retagged to complexity theory. Not sure what this has got to do with NP-Completeness.
Aryabhata
CC BY-SA 2.5
2010-08-17T16:15:38.273Z
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.
Joshua Grochow
CC BY-SA 2.5
2010-08-17T16:21:34.507Z
Isn't this covered in intro courses on computability as a typical application of Rice's theorem?
Moritz
CC BY-SA 2.5
2010-08-17T16:28:20.337Z
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}?"?
Joshua Grochow
<cc.complexity-theory><computability><turing-machines>
Can it be determined if language L lies in NP?
txwikinger
# Can it be determined if language L lies in NP?

(Asked by: username_0 on 2010-08-17)

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

**Tags:** cc.complexity-theory, computability, turing-machines

> **Comments:**
> **username_2**: Retagged to complexity theory. Not sure what this has got to do with NP-Completeness.  
> **username_3**: 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.  
> **username_4**: Isn't this covered in intro courses on computability as a typical application of Rice's theorem?  
> **username_3**: username_4 - although the yes/no answer to this question is covered by Rice's Theorem, see my answer below for more interesting results.  Maybe, username_0, you should change the question to "What is the complexity of the set {i : L(M_i) is in NP}?"?  
> **username_1**: 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.  

---

## 3 answers

### Answer by username_3 on 2010-08-17. Score: 25

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](http://dx.doi.org.proxy.uchicago.edu/10.1016/0304-3975(79)90046-X). For more, see e.g. [this article](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.8927&rep=rep1&type=ps) 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$.

> **Comments:**
> **username_5**: 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.  
> **username_3**: 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?  
> **username_5**: 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.  
> **username_6**: 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.  
> **username_6**: 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.)  

---

### Answer by username_7 on 2010-08-20. Score: 5

The answer to your literal question is no, as username_3 pointed out.
However, as username_8 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

 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
 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 by username_8 on 2010-08-18. Score: 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.

> **Comments:**
> **username_3**: 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.  

---

