Comment Important, but uses slowness of Turing Machines (Score 2) 36
YouTube lecture on this by the discoverer, Ryan Williams
Ryan Willaims's paper, "Simulating Time With Square-Root Space
This appears to be based partly but largely on
Tree Evaluation is in Space O(log n * log log n)" by James Cook and Ian Mertz (2023 colloqium,
STOC 2024 conference).
I'm just a programmer who has spent an hour or so looking at this, so please take the rest of this post with a grain of salt.
I get the impression that Professor Williams's result so far, already a tool for making progress about which computational complexity classes are the same and different, has the limitation of relying on how slow Turing machines are at accessing memory, based on the mention at 18min:50sec into that YouTube Video of how the space savings degrades for a Turing machine with tapes of more than one dimension. If I understand correctly, for such Turing machines, an algorithm with running time bounded above by time T(n) for any input of length n, the space used by this potentially much slower space-saving simulation is bounded by O( ( T(n) + log T(n) ) ** ( 1 - (1/(D+1))) ). I'm using "**" as exponentiation, so the exponent means square root (that is, exponent 0.5) for a one dimensional (linear) tape, two thirds power (exponent 0.66...) for a tape that is a two dimensional surface, 0.75th power for a three dimensional tape, and, so far, no known savings for a tree shaped tape, although I suppose that that three dimensional limit does ultimately apply to real world data storage systems.