Simulating time with square-root space

Abstract: We show that for all functions $t(n) \geq n$, every multitape Turing machine running in time $t$ can be simulated using only $O(\sqrt{t \log t})$ space. 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 at least $n^2/poly(\log n)$ time on every multitape Turing machine, thereby making a little progress on the $\text{P}$ versus $\text{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].

formal languages and automata theory

Audience: researchers in the topic

( slides | video )

One FLAT World Seminar