New proof dramatically compresses space needed for computation

(www.scientificamerican.com)

190 points baruchel | 2 comments | 27 Jun 25 13:59 UTC | HN request time: 0.534s | 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 #

1. svat ◴[30 Jun 25 16:35 UTC] No.44425220[source]▶

>>44421424 #

To be clear, this was/is a statement about the worst case, not every problem. So it may be clearer to rephrase your sentence as:

For nearly 50 years theorists believed that there exist problems taking t steps that also need roughly t/log(t) bits of memory.

(The Quanta magazine article https://www.quantamagazine.org/for-algorithms-a-little-memor... gives some context: for a long time, the best result was t/log(t) as proved in "On Time Versus Space" https://dl.acm.org/doi/10.1145/322003.322015 by Hopcroft, Paul and Valiant in 1975.)

replies(1): >>44426202 #

2. makira ◴[30 Jun 25 18:07 UTC] No.44426202[source]▶

>>44425220 (TP) #

See previous discussion: https://news.ycombinator.com/item?id=44055347

↑