Why is simulation by non deterministic Turing machine faster than a deterministic one?

Question

A deterministic universal Turing machine $U_D$ can simulate a deterministic turing machine $M_D$ in $O(T(n)log(T(n)))$ where $M_D$ runs in $O(T(n))$. But I came across an exercise in Sanjeev Arora and Boaz Barak that a non-deterministic universal Turing machine $U_{ND}$ can simulate a non deterministic Turing machine $M_{ND}$ in $O(T(n))$ where $M_{ND}$ runs in $O(T(n))$.

The hint to the exercise is that $U_{ND}$ first non deterministically guesses tape contents of $M_{ND}$ and verifies then later. But how does this help as any branch of $U_{ND}$ can simulate a branch of $M_{ND}$ in $O(T(n)log(T(n)))$, similar to the deterministic case. Am I missing something ?

Answer 1

First of all, simulation of non-deterministic universal TM is better than simulation of deterministic universal TM only time-wise. But number of parallel executing threads is very high. In parallel algorithms parlance, $T(n)$ will be smaller but another metric $T(n)P(n)$ will be higher.

Deterministic UTM has extra $\log T(n)$ factor because it has to simulate multiple working tapes in a single working tape. If we use it as a simple multiple track tape, then to simulate a single step we will need to go to and forth for maximum $T(n)$ steps. We can improve this time by a clever trick. Instead of moving heads on the multiple tracks, we keep the head of the track(s) stationary and move the content of the tracks. We also keep a gradually increasing number of interspersed blank spaces (another special blank space, instead of regular blank space) on both sides of head to do the shifting of tape content efficiently. By successfully executing this trick, each step can be simulated in amortized $O(\log T(n))$ steps.

We have to see how we can simulate non-deterministic UTM cleverly that does not require us to go to and fro, thus saving us $O(\log T(n))$ factor. Going to and fro in $k$ working tapes is the real bottleneck. We assume input and output tape are separate in both UTM and simulated TM, so they do not matter much.

Let us think how we can simulate a single work tape without going to and fro. What we do, is whenever we need to go left, we do not go left, instead we guess what is in the left, maybe 0 or may be 1 (or maybe $B$ ot may be >, beginning of tape), and proceed to the right (non-deterministically of course, for both the cases), but we write what we guessed on a work tape. Since we are not moving left correctly, we cannot know tape symbols when we move right too. So whether we move left or right, we non-deterministically guess what is under the head, make note of our guess, and move on.

After the computation is over (by a series of $T(n)$ fake or correct guesses and writings), for each thread of computation we have the content of guesses on a work tape, and we can check if the guesses and writings on the tape match in linear time $O(T(n))$ by actually going to and fro in yet another work tape. If we need our UTM not to exceed $T(n)$ execution time then we need to keep a counter for $T(n)$, some of the errant threads may go on executing for infinite time (there is a requirement on some non-deterministic TM models that every thread should stop after $T(n)$ time for acceptance, while in others only accepting threads need to stop after $T(n)$ time).

If we do this for all $k$ tapes together in a single tape, then too will be able to do this trick, but we will have to go to and fro $k$ times, one for each tape, to check if the guesses of each tape are consistent with what we are writing and what we are guessing later. This checking will take $O(kT(n))$ additional time overall for all tapes. So total running time of the non-deterministic UTM will be $O(CT(n)+kT(n))$.