New proof dramatically compresses space needed for computation
40 comments
·June 27, 2025zerof1l
heavenlyblue
Why does it need the same bits of memory as steps?
TrueDuality
Bits are a bit misleading here, it would be more accurate to say "units of computation". If you're problem space operates on 32-bit integers this would be 32bits * number of steps, these papers solve for individual bits as the smallest individual unit of computation we can commonly reason about.
mort96
Wait but if "bits of memory" here was supposed to be "units of computation", that means that:
* The old assumption was that if you require t steps to complete, you need t/log(t) units of computation
* This new proof shows that if you require t steps to complete, you need sqrt(t) units of computation
Surely this doesn't make sense? Using any definition of "unit of computation" I would intuitively assume, computing t steps requires something proportionalt to t units of computation...
mjburgess
The basic intuition of the two extremes are:
* High space requirement: we need a bucket per step to track the state
* Low space requirement: we only need a single bucket, if we can mix/unmix the various components of the state
High-space requirement algorithms will be those with a large amount of "unmixable" complex state. Low-space reqs will be those with either a small state, or an easily mixed/unmixed state.
Example of mixing: suppose we need an odd number and a parity (+,-) -- then we can store odd/even numbers: taking even to means (-1 * (number-1)) and odd means odd.
So 7 = +7, 8 = -7
I don't know if this example is really that good, but I believe the very basics of the intution is correct -- its to do with how we can trade "interpretation" of data (computation) for the amount of data in such a way that data can kinda be mixed/unmixed in the interpretation
cubefox
> Ryan Williams found that any problem solvable in time t needs only about sqrt(t) bits of memory
At least or at most or on average?
user070223
I've skimmed the result couple of weeks ago, and if I remember it states that there from all machines which takes t time to accomplish something there is one such that sqrt(t) memory is used. so it's at most but not on avg nor amorotized[not sure if et even make sense it the space where the problem lies] (you take the least memory hungry machine)
taneq
Huh? What did any of those theorists think about the phrase "time/space tradeoff"?
mhuffman
They were likely the ones that invented the phrase.
mort96
Really? But the whole idea behind the space/time trade-off is that in a bunch of cases, if you want to compute something in less memory, you need to solve it in more steps; or if you want to solve something in fewer steps, you need to use more memory.
This seems to wildly contradict the idea that the amount of memory needed is roughly proportional to the number of steps.
taneq
I'm not convinced of that if they thought that s=O(t/log(t)) where s=space (bytes or similar) and t=time (clocks, steps, etc.) I dunno about theoretical limits but in practice, there's at least 1-2 orders of magnitude to be exchanged between space and processing time.
bubblyworld
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.
zombot
> log(t)
log to what basis? 2 or e or 10 or...
Why do programmers have to be so sloppy?
anonymous_sorry
It's not sloppiness, it's economy.
You can convert between log bases by multiplying by a constant factor. But any real-world program will also have a constant factor associated with it, depending on the specific work it is doing and the hardware it is running on. So it is usually pointless to consider constant factors when theorising about computer programs in general.
12345ieee
It doesn't matter in O() notation.
derbOac
One answer, from a certain perspective, is that it's relative to your encoding base. It's logarithmic in operations, with the base depending on the encoding.
eviks
Another reason is because base e notation is ln, not log
Tarq0n
This is very common. Log without further specification can be assumed to be the natural log (log e).
holowoodman
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.
mort96
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.
griffzhowl
In information theory it usually means log base 2
eviks
no, that's what ln is for
cyrillite
One of my favourite sci comms YouTubers explained this in great detail https://youtu.be/8JuWdXrCmWg
Highly recommend
teekert
Yeah, where Hossenfelder is getting more and more dramatic (although I can still appreciate it) she has a refreshingly calm and intelligent tone indeed. Highly recommended indeed.
lherron
Thanks for this! Subscribed.
JohnKemeny
Related:
For algorithms, a little memory outweighs a lot of time. 343 points, 139 comments, 39 days ago. https://news.ycombinator.com/item?id=44055347
You need much less memory than time. 126 points, 11 comments, 22 days ago. https://news.ycombinator.com/item?id=44212855
mikewarot
I get that this is an interesting theoretical proof. I'm more interested in the inverse, trading memory for time, to make things faster, even if they take more space. It seems to me the halting problem is almost a proof the inverse of this is impossible.
Memoization is likely the best you can do.
null
LegionMammal978
The author of the paper also notes how the result gives an upper bound for how well we can 'trade space for time' in the worst case:
> In this paper, we make another step towards separating P from PSPACE, by showing that there are problems solvable in O(n) space that cannot be solved in n^2/log^c n time for some constant c > 0. [0]
Of course, this is all specifically in the context of multitape Turing machines, which have very different complexity characteristics than the RAM machines we're more used to.
trueismywork
https://arxiv.org/abs/2502.17779
Link to paper
kristianp
This seems very theoretical, just a lower bound on space required, without talking about what is being computed. Does it have any import on real algorithms?
wiz21c
Lower bound tells you how much it's worth to improve the SOTA. It gives you a hint that you can do better.
So it's more like polar star. Maybe not directly practical, but it will lead tons of people in the right direction.
Gravityloss
Thanks. I think the title is quite misleading then? I would have expected better from Scientific American.
wasabi991011
It's a reduction from multitape Turing machine to tree evaluations. If your "real algorithm" is straightforwardly modeled by a multitape TM, then it might be possible to use this proof to reduce the space. Otherwise, I don't think so.
CommenterPerson
It does have an impact. It wont give you stackoverflow like code to copy-paste though.
Analogy is thermodynamics says how efficient a heat engine _could_ be. If your engine is way below that you know there how much of an improvement there _could_ be, that it's not an impossible problem. That will get people to build better stuff.
bmacho
Upper bound on the space required. Anything, that is computable.
> Does it have any import on real algorithms?
It depends on the constants, but if the constants are good, you can have VMs for example that make memory usage smaller.
kadoban
> Does it have any import on real algorithms?
As-in algorithms you'll care about if you're a programmer and not overly interested in theory? Not really, no.
null
bluenose69
Here's a quote from the SciAm article: "Technically, that equation was t/log(t), but for the numbers involved log(t) is typically negligibly small."
Huh?
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.