Dömötör Pálvölgyi:
Complexity breakthrough: simulating \(T\) time with \(\tilde O(\sqrt T)\) space
We will sketch the main idea of the very recent breakthrough result of Ryan Williams, according to which any time-bounded computation of a Turing-machine can be simulated in much less space. More explicitly, if a decision problem can be solved on a Turing-machine (with any number of tapes) in \(t\) time, then there is a Turing-machine that solves the same problem using \(O(\sqrt{t\log t})\) space (and possibly a lot more time). This significantly improves the previous, 50-year-old best bound, which gave \(O(t/\log t)\) space. The most important ingredient of the proof is the new, 2024 Cook–Mertz tree evaluation procedure, which we plan to discuss in detail.