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 (√ 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 √ s · poly (log s ) space, and that there are explicit problems solvable in O ( n ) space which require at least n 2−ε time on every multitape Turing machine for all ε > 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].

Authors

• R. Ryan Williams

Keywords

• P versus PSPACE
• multitape Turing machine
• space complexity
• time lower bound
• tree evaluation problem