Is it NP complete to decide if a non-deterministict turing machine running on string $x$ will accept in some branch after at most $|y|$ steps?

Question

Prove that the following problem is either NP-complete or design a polynomial algorithm:

Given: Description of non-deterministic Turing machine $M$ and two string $x$ and $y$

Question: If machine $M$ runs on string $x$, will there be a branch of $M$'s computation where string $x$ is accepted for no more than $|y|$ steps?

---

I assume that this problem is NP-complete as:

1. We can run this non-deterministic machine for $|y|$ steps and see if the string is accepted
2. Wikipedia says about converting from non-deterministic to determistic Turing machine:

   Therefore, the length of an accepting computation of the DTM is, in general, exponential in the length of the shortest accepting computation of the NTM.

So the complexity would be at least $\Omega(exp(n))$. But this is a lower bound, what about the upper bound? I guess it is important for proving NP-completeness.

Answer 1

Yes, the problem is NP-complete. But your argument that this is the case doesn't work.

The property you quote in point 2 concerns a specific technique for converting a non-deterministic machine to a deterministic one. But just because that particular technique will not produce a fast solution doesn't automatically mean that there is no possible shortcut for solving this particular problem. For example, the general construction must work without knowing the running time of the nondeterministic machine; a priori it is conceivable that knowing the $|y|$ bound would allow one to do something smart and fast.

Instead, what you need to do is provide a reduction. Usually you would reduce from some known NP-complete problem to your problem, but in this case it will be more instructive to go all the way down to the definition of "NP-complete" and show that you can find a poly-time reduction from an arbitrary (not necessarily complete) problem in NP to your problem in a single, direct step.

Answer 2

In $|y|$ steps, a non-deterministic TM will make at most $|y|$ choices. So we can prove the language is in NP. Consider the verification string $w$ representing all of the non-deterministic choices of the machine. Then the algorithm for a verifier is:

• On input $M, x, y, w$, run $M$ on $x$ choosing the branches as dictated by $w$ for $|y|$ steps. Accept if $M$ accepts during this time; otherwise (if $M$ does not accept, or if we run out of choices available in $w$, reject).

The time for this algorithm is polynomial in $M$, $x$, and $y$: writing $x$ onto the tape takes polynomial in $|x|$ time, executing each step of $M$ takes polynomial in $|M|$, and there are $|y|$ steps to execute. A string is in your language if and only if the above algorithm halts for some $w$, so this is a verifier for the language.

It is also NP-complete, because we can reduce 3SAT to it by letting $M$ be a non-deterministic Turing machine which guesses an assignment of variables which might satisfy the formula, and then checks if they do. You will want $x$ to be the formula in question and $|y|$ to be some polynomial function of the number of variables of $x$. I will leave the details to you.