Improved Simulation of Nondeterministic Turing Machines

Abstract

The standard simulation of a nondeterministic Turing machine (NTM) by a deterministic one essentially searches a large bounded-degree graph whose size is exponential in the running time of the NTM. The graph is the natural one defined by the configurations of the NTM. All methods in the literature have required time linear in the size $S$ of this graph. This paper presents a new simulation method that runs in time $\widetilde{O}(\sqrt{S})$. The search savings exploit the one-dimensional nature of Turing machine tapes. In addition, we remove most of the time dependence on nondeterministic choices of states and tape head movements.

Publication
Theoretical Computer Science (Special MFCS 2010 Issue) Volume 417, pages 66–73.
Preliminary version appeared in the Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2010