*To perform a calculation a computer needs to take a number of steps which takes time, and it also needs a number of memory slots to preserve intermediate results, in other words it needs a scratchpad of a certain size. But what is the precise relationship between the two things? In **1977 it was discovered that any computation that takes X steps could be done with X/log X of memory. *
*On Time Versus Space* <https://dl.acm.org/doi/pdf/10.1145/322003.322015> *So a Computer that needed the time to do 100 time steps would need 50 memory slots, because the log of 100 is 2. That was the best we could do until February 25, 2025, that's when Ryan Williams released a paper with a surprising and very counterintuitive result that proved the required memory can be reduced dramatically to the square root of X log X. Instead of just X/log X. Thus a 100-step problem could be reduced to 15 memory slots, not 50.* *Simulating Time With Square-Root Space** <https://people.csail.mit.edu/rrw/time-vs-space.pdf> *Everybody in the field was very surprised by this result, even Williams thought it was counterintuitive: * *“It took me months to convince myself that it wasn’t just obviously false. It’s still very difficult for me to wrap my head around it. I can go through all the steps, the proof, and verify every step is correct and that it’s true. But at the end I’m still wondering.”* *Maybe it shouldn't have been too surprising, when a mathematician discovers a new proof that requires many steps he doesn't need to keep everything he has done in previous steps in short term memory to complete the next step. Anyway, now we can look for trade-offs between time needed and memory space. * * John K Clark See what's on my new list at Extropolis <https://groups.google.com/g/extropolis>* tmr -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to everything-list+unsubscr...@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/everything-list/CAJPayv3WWZwmpvs0_s02OSbHHbNi00WUNPsE5sR7%2BbpWU5iaXw%40mail.gmail.com.
