Simulating Time in Square-Root Space

by Ryan Williams

Oded's comments

The core of this result is the observation that a $t$-time computation of a $k$-tape TM can be reduced to a Tree Evaluation problem for an $O(k)$-ary tree of height $h$ and strings of length $\ell=O(t/h)$. This reduction is easier to see in the case of oblivious TMs, but holds also in general. (Recall, however, that a $t$-time computation of a $k$-tape TM can be emulated by an oblivious $O(t log t)$-time 2-tape TM.) In any case, using the amazing $O(\ell+h\log\ell)$-space algorithm of Cook and Mertz (see also my exposition), one gets the claimed result.

Note that the small improvement presented HERE is in terms of $\ell+h$ (i.e., it yields $o((\ell+h)\log(\ell+h))$) and is not applicable when $\ell \gg h$, as is the case here (i.e., using $\ell=\sqrt(t\log t)$ and $h-\sqrt(t/\log t)$)

Original abstract

We show that for all functions $t(n) \geq n$, every multitape Turing machine running in time $t$ can be simulated in space only $O(\sqrt{t \log t})$. This is a substantial improvement over Hopcroft, Paul, and Valiant's simulation of time $t$ in $O(t/\log t)$ space from 50 years ago [FOCS 1975, JACM 1977]. Among other results, our simulation implies that bounded fan-in circuits of size $s$ can be evaluated on any input in only $\sqrt{s} \cdot poly(\log s)$ space, and that there are explicit problems solvable in $O(n)$ space which require $n^{2-\varepsilon}$ time on a multitape Turing machine for all $\varepsilon > 0$, thereby making a little progress on the $P$ versus $PSPACE$ problem.

Our simulation reduces the problem of simulating time-bounded multitape Turing machines to a series of implicitly-defined Tree Evaluation instances with nice parameters, leveraging the remarkable space-efficient algorithm for Tree Evaluation recently found by Cook and Mertz [STOC 2024].

See ECCC TR25-017.


Back to list of Oded's choices.