# Finding the Length of the shortest Accepting path of a NDTM

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.

• 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 Feb 7 '12 at 8:54
• 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 Feb 7 '12 at 11:11
• 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 Feb 7 '12 at 19:04
• @Bruno , Tks a lot - Do make your comment an answer. – Xavier Labouze Feb 7 '12 at 20:34

Your problem is $\mathsf{NP}$-complete, and you can find a proof for instance here (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}$.

• 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 Feb 8 '12 at 23:35
• I edited the question to focus on the shortest accepting path only. I don't think it changes your answer, does it ? – Xavier Labouze Feb 10 '12 at 11:09
• 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 Feb 10 '12 at 12:05
• Yes I wonder too - tks ! – Xavier Labouze Feb 10 '12 at 12:58

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$