Simulating Time with Square-Root Space
Journal of the ACM · 30.06.2026 · 73 (3) · 1-25
DOI: 10.1145/3798104 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 16.06.2026. Verfasst von Ryan Williams. Die Arbeit nennt 57 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NSF.
Abstract (Originalsprache)
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].
Förderung
- NSF
Zitieren
APA
Williams, R. (2026). Simulating Time with Square-Root Space. Journal of the ACM, 73(3), 1-25. https://doi.org/10.1145/3798104
Vancouver
Williams R. Simulating Time with Square-Root Space. Journal of the ACM. 2026;73(3):1-25. doi:10.1145/3798104
BibTeX
@article{Williams2026,
author = {Williams, Ryan},
title = {Simulating Time with Square-Root Space},
journal = {Journal of the ACM},
year = {2026},
volume = {73},
number = {3},
pages = {1--25},
doi = {10.1145/3798104}
}
EUVIMED