Improved simulation of nondeterministic Turing machines
| Autor: | Richard J. Lipton, Kenneth W. Regan, Farbod Shokrieh, Subrahmanyam Kalyanasundaram |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Theoretical computer science General Computer Science DTIME Computational complexity theory 2-EXPTIME Computer science Probabilistic Turing machine Super-recursive algorithm EXPTIME Description number DSPACE Turing machines Computer Science::Computational Complexity Theoretical Computer Science law.invention Turing machine symbols.namesake Non-deterministic Turing machine law Nondeterminism PSPACE Determinism Linear bounded automaton Linear speedup theorem Turing machine examples NSPACE Complexity NP Nondeterministic algorithm Turing reduction symbols Universal Turing machine Time hierarchy theorem Algorithm Simulation Algorithms Computer Science::Formal Languages and Automata Theory Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 417:66-73 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2011.05.018 |
| Popis: | 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 choices of states and tape head movements. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect