Some Time-Space Tradeoff Results Concerning Single-Tape and Offline TM’ s
Óscar H. Ibarra, Shlomo Moran · SIAM Journal on Computing · 1983
Fast simulations of time-bounded single-tape TM’s and offline TM’s (i.e., TM’s with a two-way read-only input and one storage tape) by space-bounded TM’s of the same type are presented. The following results are shown: (1) Any language accepted by a single-tape TM in time $T(n) \geqq n^2 $ can be accepted by a single-tape TM in space $T^{1/2} (n)$ and time $T^2 (n)$. (2) Any language accepted by an offline TM in time $T(n) \geqq n $ can be accepted by an offline TM in space $(T(n)\log n)^{1/2} $ and time $T^{3/2} (n)(T^{1/2} (n) + n/(\log n)^{1/2} )$. Similar (in fact, in some sense, stronger) results hold for nondeterministic TM’s. For example: (3) Any language accepted by a single-tape nondeterministic TM in time $T(n) \geqq n^2 $ can be accepted by a single-tape nondeterministic TM in space $S(n)$ and time $T^2 (n)/S(n)$ for any $T^{1/2} (n) \leqq S(n) \leqq T(n)$. Similar time-space tradeoffs hold for TM’s with a multidimensional storage tape. Previously known results on simulation of time bounded by space bounded TM’s had exponential (in $T(n)$) time complexity.