<p>Your problem is $\mathsf{NP}$-complete, and you can find a proof for instance <a href="http://www.cs.uml.edu/~wang/cs502/tiling.pdf">here</a> (I gave a sketch in comments). </p>

<p>A remark: If you consider $\{\langle M,x,t\rangle : M$ halts on $x$ in $t$ steps $\}$, then you can only show it is $\mathsf{NP}$-hard. But as you mention that you consider $t$ polynomially bounded (in the sizes of $M$ and $x$, I guess), then your problem belongs to $\mathsf{NP}$.</p>

CC BY-SA 3.0
2012-02-08T23:35:01.230Z
tks for the link - a NDTM halts as soon as possible, so when I say it halts in $t$ steps, I mean there is no accepting path in less than $t$ steps. Is the answer still NP-complete if we consider only the shortest accepting path (I should have been more precise on this point...)
Xavier Labouze
CC BY-SA 3.0
2012-02-10T11:09:44.347Z
I edited the question to focus on the shortest accepting path only. I don't think it changes your answer, does it ?
Xavier Labouze
CC BY-SA 3.0
2012-02-10T12:05:32.810Z
It remains $\mathsf{NP}$-hard: It is "easy" to make a NDTM that solves SAT with all paths (accepting and rejecting) of the exact same length. This gives a reduction from SAT to your problem. For an upper bound, it is in $\Pi_2^p$, but I wonder if it belongs to $\mathsf{NP}$.
Bruno
CC BY-SA 3.0
2012-02-10T12:58:08.070Z
Yes I wonder too - tks !
Xavier Labouze
CC BY-SA 3.0
2012-02-08T22:05:03.143Z
2012-02-08T22:05:03.143Z
Bruno
<p>see also thm 5.15 p61 of <a href="http://www.nada.kth.se/~johanh/complexitylecturenotes.pdf" rel="nofollow">Hastad's Complexity Theory</a>:</p>

<p>Given a set $A,$ then $A \in \mathsf{NP}$ iff there is a language $B \in \mathsf{P}$
and a constant $k$ such that</p>

<p>$x \in A \Leftrightarrow \exists_{y,|y|\leq|x|^ k}(x, y) \in B$</p>

CC BY-SA 3.0
2012-02-08T23:16:48.890Z
Tks for the reference.
Xavier Labouze
CC BY-SA 3.0
2012-02-08T22:31:25.813Z
2012-02-08T22:31:25.813Z
vzn
<p>Let $M$ be a NDTM (non deterministic Turing machine) which decides a certain NP-complete language, say SAT.</p>

<p>$M$ computes any instance $I$ of the NP-complete problem in at most $p(n)$ non deterministic steps ($p$ in a polynomial function, $n$ is the input size). The length of a computation path can be measured as the "rank" of the non deterministic step where $M$ halts. Let call $rank_M(I)$  the rank of the shortest accepting path ($rank_M(I)$ is $p(n)+1$ if $M$ rejects $I$).</p>

<p>Is this problem NP-complete : Given a boolean expression $I$, is it true that $rank_M(I)=k$ ? ($k$ is polynomially bounded in $n$)</p>

<p>Edit --- $rank_M(I)$ has been modified : it defines now the shortest accepting path (instead of just the rank of the step where $M$ halts).</p>

<p>Thank you. </p>

CC BY-SA 3.0
2012-02-07T08:54:25.290Z
I am not sure what you mean by *rank*. If I am right, you mean the exact step when the TM halts on a particular input. Nevertheless, the following problem is $\mathsf{NP}$-complete: Given a NDTM $M$, an input $x$ and a time bound $t$, does $M$ halts on $x$ in at most $t$ computation steps. Does this help?
Bruno
CC BY-SA 3.0
2012-02-07T11:11:36.503Z
Yes, you are right. My post deals with $t$ polynomially bounded in the size of $x$ and the problem is "does $M$ halt on $x$ in exactly $t$ computation steps?" - Can it be considered NP-complete as well ? (since the "rank" of the computation step is directly accessible)
Xavier Labouze
CC BY-SA 3.0
2012-02-07T19:04:59.460Z
I guess so. Let $L\in\mathsf{NP}$. It is decided by a NDTM $M$ in time $p(n)$. To turn an instance of $L$ into an instance of your problem, I do the following: I add a counter to $M$, and when on input $x$ it enters an accepting state, it loops until the counter reaches $p(|x|)$. Let $\tilde M$ be this NDTM. We have $x\in L\iff \tilde M$ halts on $x$ in exactly $p(|x|)$ computation steps. This gives a polytime reduction from any language $L\in\mathsf{NP}$ to your problem.
Bruno
CC BY-SA 3.0
2012-02-07T20:34:47.193Z
@Bruno , Tks a lot - Do make your comment an answer.
Xavier Labouze
<cc.complexity-theory><complexity-classes><sat><counting-complexity><turing-machines>
Finding the Length of the shortest Accepting path of a NDTM
Xavier Labouze
# Finding the Length of the shortest Accepting path of a NDTM

(Asked by: username_0 on 2012-02-07)

Let $M$ be a NDTM (non deterministic Turing machine) which decides a certain NP-complete language, say SAT.

$M$ computes any instance $I$ of the NP-complete problem in at most $p(n)$ non deterministic steps ($p$ in a polynomial function, $n$ is the input size). The length of a computation path can be measured as the "rank" of the non deterministic step where $M$ halts. Let call $rank\_M(I)$ the rank of the shortest accepting path ($rank\_M(I)$ is $p(n)+1$ if $M$ rejects $I$).

Is this problem NP-complete : Given a boolean expression $I$, is it true that $rank\_M(I)=k$ ? ($k$ is polynomially bounded in $n$)

Edit --- $rank\_M(I)$ has been modified : it defines now the shortest accepting path (instead of just the rank of the step where $M$ halts).

Thank you.

**Tags:** cc.complexity-theory, complexity-classes, sat, counting-complexity, turing-machines

> **Comments:**
> **username_1**: I am not sure what you mean by *rank*. If I am right, you mean the exact step when the TM halts on a particular input. Nevertheless, the following problem is $\mathsf{NP}$-complete: Given a NDTM $M$, an input $x$ and a time bound $t$, does $M$ halts on $x$ in at most $t$ computation steps. Does this help?  
> **username_0**: Yes, you are right. My post deals with $t$ polynomially bounded in the size of $x$ and the problem is "does $M$ halt on $x$ in exactly $t$ computation steps?" - Can it be considered NP-complete as well ? (since the "rank" of the computation step is directly accessible)  
> **username_1**: I guess so. Let $L\in\mathsf{NP}$. It is decided by a NDTM $M$ in time $p(n)$. To turn an instance of $L$ into an instance of your problem, I do the following: I add a counter to $M$, and when on input $x$ it enters an accepting state, it loops until the counter reaches $p(|x|)$. Let $\tilde M$ be this NDTM. We have $x\in L\iff \tilde M$ halts on $x$ in exactly $p(|x|)$ computation steps. This gives a polytime reduction from any language $L\in\mathsf{NP}$ to your problem.  
> **username_0**: @username_1 , Tks a lot - Do make your comment an answer.  

---

## 2 answers

### Answer by username_1 on 2012-02-08. Score: 8 | Accepted answer

Your problem is $\mathsf{NP}$-complete, and you can find a proof for instance [here](http://www.cs.uml.edu/~wang/cs502/tiling.pdf) (I gave a sketch in comments).

A remark: If you consider $\{\langle M,x,t\rangle : M$ halts on $x$ in $t$ steps $\}$, then you can only show it is $\mathsf{NP}$-hard. But as you mention that you consider $t$ polynomially bounded (in the sizes of $M$ and $x$, I guess), then your problem belongs to $\mathsf{NP}$.

> **Comments:**
> **username_0**: tks for the link - a NDTM halts as soon as possible, so when I say it halts in $t$ steps, I mean there is no accepting path in less than $t$ steps. Is the answer still NP-complete if we consider only the shortest accepting path (I should have been more precise on this point...)  
> **username_0**: I edited the question to focus on the shortest accepting path only. I don't think it changes your answer, does it ?  
> **username_1**: It remains $\mathsf{NP}$-hard: It is "easy" to make a NDTM that solves SAT with all paths (accepting and rejecting) of the exact same length. This gives a reduction from SAT to your problem. For an upper bound, it is in $\Pi_2^p$, but I wonder if it belongs to $\mathsf{NP}$.  
> **username_0**: Yes I wonder too - tks !  

---

### Answer by username_2 on 2012-02-08. Score: 0

see also thm 5.15 p61 of [Hastad's Complexity Theory](http://www.nada.kth.se/~johanh/complexitylecturenotes.pdf):

Given a set $A,$ then $A \in \mathsf{NP}$ iff there is a language $B \in \mathsf{P}$
and a constant $k$ such that

$x \in A \Leftrightarrow \exists\_{y,|y|\leq|x|^ k}(x, y) \in B$

> **Comments:**
> **username_0**: Tks for the reference.  

---

