TY - GEN
T1 - Improved simulation of nondeterministic Turing machines
AU - Kalyanasundaram, Subrahmanyam
AU - Lipton, Richard J.
AU - Regan, Kenneth W.
AU - Shokrieh, Farbod
PY - 2010
Y1 - 2010
N2 - 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 Õ(√S). The search savings exploit the one-dimensional nature of Turing machine tapes. In addition, we remove most of the time-dependence on nondeterministic choice of states and tape head movements.
AB - 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 Õ(√S). The search savings exploit the one-dimensional nature of Turing machine tapes. In addition, we remove most of the time-dependence on nondeterministic choice of states and tape head movements.
UR - https://www.scopus.com/pages/publications/78349233087
U2 - 10.1007/978-3-642-15155-2_40
DO - 10.1007/978-3-642-15155-2_40
M3 - Conference contribution
AN - SCOPUS:78349233087
SN - 364215154X
SN - 9783642151545
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 453
EP - 464
BT - Mathematical Foundations of Computer Science 2010 - 35th International Symposium, MFCS 2010, Proceedings
T2 - 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010
Y2 - 23 August 2010 through 27 August 2010
ER -