Simulating Time with Square-Root Space
Ryan Williams · Journal of the ACM · 2025
We show that for all functions \(t(n) \ge 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 \text{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 \gt 0\) , thereby making a little progress on the \({\sf P}\) versus \({\sf 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].