Simulating Time With Square-Root Space

2025/02/25 by Ryan Williams, R. Ryan Williams, Williams, R. Ryan · 15 voices · 6 citations
Computer Science · Mathematics · #Matrix Theory and Algorithms #Computer Graphics and Visualization Techniques #Algebraic and Geometric Analysis

paper · pdf · doi:10.48550/arxiv.2502.17779

Abstract

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 n^2-ε time on a 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].

Cited by

• On the complexity of computing Strahler numbers
• Derandomizing Isolation In Catalytic Logspace
• On the Holographic Geometry of Deterministic Computation
• Unconditional Time and Space Complexity Lower Bounds for Intersection Non-Emptiness
• Linear Matroid Intersection is in Catalytic Logspace
• Zero-Knowledge Proofs in Sublinear Space

Discussions

• Simulating Time with Square-Root Space [hn, 20 points, 1 comments]
• "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, & Valiant's simula [bsky, 8 points, 0 comments]
• Simulating Time with Square-Root Space [hn, 3 points, 0 comments]
• #arXiv Simulating Time With Square-Root Space arxiv.org/abs/2502.17779 ∀ t(n)≥n, every multitape Turing machine running in time t can be simulated in space only O(sqrt(t log t)), a substantial improve [bsky, 3 points, 1 comments]
• arxiv.org/abs/2502.17779 [bsky, 2 points, 0 comments]
• Something almost incredible regarding time and memory size www.quantamagazine.org/for-algorith... arxiv.org/abs/2502.17779 [bsky, 2 points, 1 comments]
• Simulating Time with Square-Root Space [hn, 2 points, 0 comments]
• Simulating time with square-root space [hn, 2 points, 0 comments]
• Simulating Time with Square-Root Space [hn, 2 points, 0 comments]
• 専門外なんで分からんのですが、これどうなんですかね arxiv.org/abs/2502.17779 [bsky, 0 points, 0 comments]
• Simulating Time with Square-Root Space #HackerNews https://arxiv.org/abs/2502.17779 [bsky, 0 points, 0 comments]
• Simulating Time with Square-Root Space https://arxiv.org/abs/2502.17779 [bsky, 0 points, 0 comments]
• So, how Ryan Williams' Simulating Time With Square-Root Space affects time-memory trade-off (TMTO) attacks, in practice? arxiv.org/abs/2502.17779 #cryptanalysis [bsky, 0 points, 0 comments]
• arxiv.org/abs/2502.17779 [bsky, 0 points, 1 comments]
• Paper link: arxiv.org/abs/2502.17779 [bsky, 0 points, 0 comments]

Related

• Improved Bounds on the Space Complexity of Circuit Evaluation
• Is Space a Stronger Resource than Time? Positive Answer for the Nondeterministic at-Least-Quadratic Time Case
• Space and Time Complexity for Infinite Time Turing Machines
• Efficient Turing Machine Simulation with Transformers
• Program-Size Versus Time Complexity, Speed-Up and Slowdown Phenomena in Small Turing Machines