←back to thread

New proof dramatically compresses space needed for computation

(www.scientificamerican.com)
190 points baruchel | 9 comments | 27 Jun 25 13:59 UTC | HN request time: 0.973s | source | bottom
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. 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 #
2. griffzhowl ◴[30 Jun 25 12:36 UTC] No.44422511[source]▶
In information theory it usually means log base 2
3. eviks ◴[30 Jun 25 12:59 UTC] No.44422753[source]▶
no, that's what ln is for
replies(1): >>44427512 #
4. holowoodman ◴[30 Jun 25 13:11 UTC] No.44422859[source]▶
No. Usually log without further specification is base10.

Except in mathematics and physics, where it usually is base e.

Except sometimes in computer science, where it can be base 2.

But there are more of those weirdnesses: "ld" can be "log decimal", so base 10; or "logarithmus dualis", so base 2. Base 2 is also sometimes written as "lb" (log binary). You really need to know the conventions of the field/subfield to know which is which.

replies(2): >>44424688 #>>44426960 #
5. mort96 ◴[30 Jun 25 13:53 UTC] No.44423290[source]▶
In this case, and in many other cases, log without further specification is meant to be understood as just "it is logarithmic" without further specification. With big O, we don't differentiate between log bases, just as we don't differentiate between scale factors. In fact, converting from one log base to another is just multiplying by a constant.
6. eru ◴[30 Jun 25 15:46 UTC] No.44424688[source]▶
Log without a basis (at least to me) usually indicates that the basis doesn't matter in this context (or is obvious).

I usually see either base e or base 2 as the default. In which applications do people use both logarithms and base 10 as the default? I mean, especially these day. In the olden days of the slide ruler base 10 was probably more common.

replies(1): >>44426557 #
7. holowoodman ◴[30 Jun 25 18:47 UTC] No.44426557{3}[source]▶
> In which applications do people use both logarithms and base 10 as the default?

Engineering. For example dB is defined in base 10.

8. gbacon ◴[30 Jun 25 19:28 UTC] No.44426960[source]▶
Base 2 is also sometimes abbreviated lg.
9. 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.