Simulating Time With Square-Root Space

R. Ryan Williams

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 improvem…