←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: 0s | 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 #
Tarq0n ◴[30 Jun 25 12:34 UTC] No.44422485[source]▶
This is very common. Log without further specification can be assumed to be the natural log (log e).
replies(4): >>44422511 #>>44422753 #>>44422859 #>>44423290 #
eviks ◴[30 Jun 25 12:59 UTC] No.44422753[source]▶
no, that's what ln is for
replies(1): >>44427512 #
1. thaumasiotes ◴[30 Jun 25 20:30 UTC] No.44427512[source]▶
Well, you're right that that's what "ln" is for. But more specifically "ln" is for indicating the natural log on calculators that already have another button labeled "log". Tarq0n is correct that "log" without further specification can be assumed to be the natural log.