6
$\begingroup$

I have one simple question:

There is a set, which can be decided in polynomial time by a (one-band) non-deterministic Turing Machine.

Why should there exist one (one-band) non-deterministic Turing Machine, which decides the same set, but with the additional property: There exists one natural number k, such that all the possible calculations last exactly n^k steps, if the input has the length n?

This is one "without-loss-of-generality-assumption" in the proof of a theorem. (namely the proof of the Theorem of Fagin which says: "ESO captures NP")

I cannot understand it. How can we manipulate the first machine to get the second machine?

Improve this question
$\endgroup$
7
  • $\begingroup$ Since the language lies in P, the time is bounded above by n^k for some k. If we need exactly n^k, we can assume that our machine makes additional moves. $\endgroup$
    – user2171
    Commented Jul 23, 2011 at 17:18
  • 1
    $\begingroup$ It is not always possible to do. Take $n=1$ and suppose that the accepting computations on a 1-letter input have length at least 2. $\endgroup$
    – user6976
    Commented Jul 23, 2011 at 17:23
  • $\begingroup$ ok, I forgot to say that n>1. $\endgroup$
    – tibet
    Commented Jul 23, 2011 at 17:37
  • $\begingroup$ to the comment of AIB: Yes this is the problem. But how does the machine know the number of steps. It has to count the number of steps during the calculation and if it stops earlier then n^k (by input length n) then it should make theese additional (dummy) steps and then stop. But how? Given one Language in NP, how can I show that there is one NTM which stops exactly after n^k steps for every input of lentgh n? $\endgroup$
    – tibet
    Commented Jul 23, 2011 at 17:44
  • $\begingroup$ @tibet, the overhead of step counting is tolerable, it could be a logarithmic counter, etc. But the exact details must be tedious, especially if you want to do that on a one-tape machine. $\endgroup$
    – user2171
    Commented Jul 23, 2011 at 17:57

1 Answer 1

Reset to default
6
$\begingroup$

This is possible, but it is somewhat tricky to do. Here is an outline of one way to do it...

Start with your original one-tape Turing machine $M_0$ which runs in time $\leq k + n^k$ (say) on input of length $n$.

First create a two-tape Turing machine $M_1$ which simulates $M_0$ on one tape and keeps track of a step-counter on the other tape. The counter is initially set to value $k + n^k$ and is decremented at each simulation step. When the simulation of $M_0$ terminates, $M_1$ keeps doing dummy moves until the counter is exhausted. Thus $M_1$ runs in exactly the same time on every input of length $n$.

Finally, we simulate $M_1$ on a one-tape Turing machine $M_2$ as follows. Think of even cells as belonging to the first tape of $M_1$ and odd cells as belonging to the second tape of $M_1$. To keep track of where the two $M_1$ heads, each symbol will now have a plain and a red variant; there will be only two red variants at any given time and they will mark the two head positions.

It is straightforward to simulate $M_1$ on such a tape, but the simpler ways do not simulate each step of $M_1$ in a constant number of steps since switching from one head to the other requires a variable number of moves. To remedy this, first note that $M_1$ uses less than $\ell + n^\ell$ cells of the tape for some $\ell$ that can be effectively estimated from $k$ and the above transformations. When it starts, $M_2$ reads the input length $n$ and places a freshly minted marker on the $(\ell + n^\ell)$-th cell, beyond any cell required to simulate $M_1$. Whenever $M_2$ simulates a step of $M_1$, it proceeds as follows:

  • Starting at the base of the tape, $M_2$ finds the appropriate tape head (red symbol in even/odd position).

  • $M_2$ then performs the appropriate action to simulate $M_1$, these each take a fixed finite amount of steps which may vary from operation to operation. Once this is completed, $M_2$ dances around a little so that it returns to the original tape position exactly 1001 steps after it arrived there.

  • Then $M_2$ moves right until it finds the marker at position $\ell + n^\ell$ at which point it turns around and returns to the base of the tape.

Although this is very inefficient, $M_2$ does correctly simulate $M_1$ and it takes exactly the same amount of time to simulate each step of $M_1$. Furthermore, $M_2$ still runs in polynomial time, though the polynomial is much worse than the original $k + n^k$.

Edit: This answer was simplified from its original version.

Improve this answer
$\endgroup$
1
  • $\begingroup$ A k-band NTM which runs in time t(n) can be simuleted by a 1-band NTM which uses time t(n)^2. I think the proof uses the same argument as yours. $\endgroup$
    – tibet
    Commented Jul 24, 2011 at 21:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .