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.

  • 2
    $\begingroup$ 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? $\endgroup$ – Bruno Feb 7 '12 at 8:54
  • $\begingroup$ 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) $\endgroup$ – Xavier Labouze Feb 7 '12 at 11:11
  • 4
    $\begingroup$ 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. $\endgroup$ – Bruno Feb 7 '12 at 19:04
  • 1
    $\begingroup$ @Bruno , Tks a lot - Do make your comment an answer. $\endgroup$ – 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}$.

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

see also thm 5.15 p61 of Hastad's Complexity Theory:

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$

  • $\begingroup$ Tks for the reference. $\endgroup$ – Xavier Labouze Feb 8 '12 at 23:16

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.