Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
Lists
Only you see this
Abstract
Every single-tape Turing machine (TM) of time complexity $T(n) \geqq n^{2}$ can be simulated by a single-tape TM in space $T^{{1 / 2}}(n)$. It is shown that the time of the simulation can be bounded by $T^{3/2}(n)$ in the case of deterministic TMs and by $T(n)$ in the case of nondeterministic ones. Similar results are shown for off-line machines and for machines with multidimensional tape.
BibTeX
@article{liskiewicz1990fast,
author = {Maciej Liskiewicz and Krzysztof Lorys},
title = {{Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones}},
journal = {SIAM Journal on Computing},
year = {1990},
doi = {10.1137/0219034},
}Loading related content...