←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.287s | 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 #
zombot ◴[30 Jun 25 12:19 UTC] No.44422352[source]▶
> log(t)

log to what basis? 2 or e or 10 or...

Why do programmers have to be so sloppy?

replies(5): >>44422370 #>>44422485 #>>44422742 #>>44422905 #>>44422929 #
1. 12345ieee ◴[30 Jun 25 12:20 UTC] No.44422370[source]▶
It doesn't matter in O() notation.