Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > P VERSUS PSPACE:
Reports tagged with P versus PSPACE:
TR25-017 | 24th February 2025
Ryan Williams

Simulating Time in Square-Root Space

We show that for all functions t(n) \geq 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, ... more >>>




ISSN 1433-8092 | Imprint