←back to thread

New proof dramatically compresses space needed for computation

(www.scientificamerican.com)
190 points baruchel | 1 comments | 27 Jun 25 13:59 UTC | HN request time: 0.208s | source
Show context
zerof1l ◴[30 Jun 25 10:05 UTC] No.44421424[source]▶
Here's the gist:

For nearly 50 years theorists believed that if solving a problem takes t steps, it should also need roughly t bits of memory: 100 steps - 100bits. To be exact t/log(t).

Ryan Williams found that any problem solvable in time t needs only about sqrt(t) bits of memory: a 100-step computation could be compressed and solved with something on the order of 10 bits.

replies(7): >>44422352 #>>44422406 #>>44422458 #>>44422855 #>>44423750 #>>44424342 #>>44425220 #
taneq ◴[30 Jun 25 12:30 UTC] No.44422458[source]▶
Huh? What did any of those theorists think about the phrase "time/space tradeoff"?
replies(2): >>44422643 #>>44422948 #
1. bubblyworld ◴[30 Jun 25 13:18 UTC] No.44422948[source]▶
That phrase is usually about a specific problem, right? This is more like given an arbitrary algorithm (you don't know which up front), can you optimise it's memory usage? Seems kinda surprising to me that you can.