$\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression

Logan Nye

We prove a square-root space simulation for deterministic multitape Turing machines, showing $\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ \emph{measured in tape cells ov…