Simulating Time With Square-Root Space

We show that for all functions t(n)≥n, every multitape Turing machine running in time t can be simulated in space only O(tlogt‾‾‾‾‾√). This is a substantial improvement over Hopcroft, Paul, and Valiant's simulation of time t in O(t/logt) space from about 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 s√⋅\poly(logs) space, and that there are explicit problems solvable in O(n) space which require essentially n2 time on a multitape Turing machine, thereby making a little progress on the P versus PSPACE problem.

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