3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 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
    Commented Feb 7, 2012 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
    Commented Feb 7, 2012 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
    Commented Feb 7, 2012 at 19:04
  • 1
    $\begingroup$ @Bruno , Tks a lot - Do make your comment an answer. $\endgroup$
    – Xavier Labouze
    Commented Feb 7, 2012 at 20:34

2 Answers 2

Reset to default
8
$\begingroup$

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}$.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Feb 8, 2012 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
    Commented Feb 10, 2012 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
    Commented Feb 10, 2012 at 12:05
  • $\begingroup$ Yes I wonder too - tks ! $\endgroup$
    – Xavier Labouze
    Commented Feb 10, 2012 at 12:58
0
$\begingroup$

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$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Tks for the reference. $\endgroup$
    – Xavier Labouze
    Commented Feb 8, 2012 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.