See previous discussion:
<a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=44055347">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=44055347</a>

To be clear, this was&#x2F;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&#x2F;log(t) bits of memory.(The Quanta magazine article <a href="https:&#x2F;&#x2F;www.quantamagazine.org&#x2F;for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.quantamagazine.org&#x2F;for-algorithms-a-little-memor...</a> gives some context: for a long time, the best result was t&#x2F;log(t) as proved in &quot;On Time Versus Space&quot; <a href="https:&#x2F;&#x2F;dl.acm.org&#x2F;doi&#x2F;10.1145&#x2F;322003.322015" rel="nofollow">https:&#x2F;&#x2F;dl.acm.org&#x2F;doi&#x2F;10.1145&#x2F;322003.322015</a> by Hopcroft, Paul and Valiant in 1975.)

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&#x2F;unmix the various components of the stateHigh-space requirement algorithms will be those with a large amount of &quot;unmixable&quot; complex state. Low-space reqs will be those with either a small state, or an easily mixed&#x2F;unmixed state.Example of mixing: suppose we need an odd number and a parity (+,-) -- then we can store odd&#x2F;even numbers: taking even to means (-1 * (number-1)) and odd means odd.So 7 = +7, 8 = -7I don&#x27;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 &quot;interpretation&quot; of data (computation) for the amount of data in such a way that data can kinda be mixed&#x2F;unmixed in the interpretation

Bits are a bit misleading here, it would be more accurate to say &quot;units of computation&quot;. If you&#x27;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.

Why does it need the same bits of memory as steps?

As I understand it, this result is about algorithms that solve any instance of a given computational problem (like finding the shortest paths through a graph.) The specific problem instance (the graph) is the input to the algorithm. The result shows how to take an algorithm and construct another algorithm that solves the same class of problems in less space, by transforming how the algorithm reads and writes memory. Now you have an algorithm that still solves any instance of that problem but uses only sqrt(t) space.So, to answer your question more directly: no, you don&#x27;t have to have solved a specific instance of the problem, but you have to already have an algorithm that solves it in general.

&gt; 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.Does it require one to first have solved the problem in uncompressed space?

I&#x27;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&#x27;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)

&gt; Ryan Williams found that any problem solvable in time t needs only about sqrt(t) bits of memoryAt least or at most or on average?

That phrase is usually about a specific problem, right? This is more like given an arbitrary algorithm (you don&#x27;t know which up front), can you optimise it&#x27;s memory usage? Seems kinda surprising to me that you can.

They were likely the ones that invented the phrase.

Huh? What did any of those theorists think about the phrase &quot;time&#x2F;space tradeoff&quot;?

Doesn’t make practical sense why they would even assign a number to problems which could have unknown dependencies. Unless you are talking about bounded math issues

It&#x27;s not sloppiness, it&#x27;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.

It doesn&#x27;t matter in O() notation.

One answer, from a certain perspective, is that it&#x27;s relative to your encoding base. It&#x27;s logarithmic in operations, with the base depending on the encoding.

Another reason is because base e notation is ln, not log

This is very common. Log without further specification can be assumed to be the natural log (log e).

&gt; log(t)log to what basis? 2 or e or 10 or...Why do programmers have to be so sloppy?

Here&#x27;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&#x2F;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.

She has taken to click bait -- e.g., using the word &quot;shocking&quot; and showing pictures with here mouth open (actually she can&#x27;t really open her mouth, but you get the idea).

Sabine Hossenfelder also has very &#x27;interesting&#x27; ideas about determinism.

Yeah, where Hossenfelder is getting more and more dramatic (although I can still appreciate it) she has a refreshingly calm and intelligent tone. Highly recommended indeed.

One of my favourite sci comms YouTubers explained this in great detail <a href="https:&#x2F;&#x2F;youtu.be&#x2F;8JuWdXrCmWg" rel="nofollow">https:&#x2F;&#x2F;youtu.be&#x2F;8JuWdXrCmWg</a>Highly recommend

The result doesn&#x27;t actually apply to _all_ algorithms, only oblivious ones. Oblivious algorithms are ones where step i does not depend on decisions made in steps j &lt; i. Almost all useful algorithms are non-oblivious, with some notable exceptions [1]. This work is a step forward towards proving the result for the general case, with little practical usage (and that&#x27;s perfectly okay).[1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Sorting_network" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Sorting_network</a>

This is blue skies research and is not expected to have any immediate practical impact whatsoever.

I am trying to understand how the paper OP posted can be translated into anything that improves current algorithms.Can actually any current algorithms improved by this??
Or is that only the case if the hardware itself is improved?I am baffled

Related:For algorithms, a little memory outweighs a lot of time.
343 points, 139 comments, 39 days ago.
<a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=44055347">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=44055347</a>You need much less memory than time.
126 points, 11 comments, 22 days ago.
<a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=44212855">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=44212855</a>

The author of the paper also notes how the result gives an upper bound for how well we can &#x27;trade space for time&#x27; in the worst case:&gt; 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&#x2F;log^c n time for some constant c &gt; 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&#x27;re more used to.[0] <a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;2502.17779" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;2502.17779</a>

Dynamic programming and divide-and-conquer with multiple cores on a diagonalized problem space of independent problems (CPU and memory hierarchy) with (hopefully) a final reduce step at the end. Real-world problems are seldom so neat, hence the investment in Infiniband gear.

I get that this is an interesting theoretical proof. I&#x27;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.

<a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;2502.17779" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;2502.17779</a>Link to paper

I’ve spent many years working on hpc problems, and most people simply don’t have , or don’t care about, or don’t know what to do with performance problems.Don’t have to because they usually have a full machine, and unless they saturate it, the problem doesn’t exist.Don’t care, because many people think it’s alright if things are slow, or inefficient ( the user can wait, or will live with 100ms instead of 1ms).Don’t know what to do - this one is interesting : many people don’t realize it’s actually possible to get the same result , but faster.

I&#x27;m also surprised by how many developers just don&#x27;t seem to care much.Yet, the general population isn&#x27;t behaving like scouts most of the time, so I suppose it&#x27;s only fair that developers also aren&#x27;t.&quot;Leave the world a better place than you found it&quot; (s&#x2F;world&#x2F;code&#x2F;g)

Given your username, I&#x27;m sure whoever inherits your codebase would share the same sentiment.

It&#x27;s also trained on all best practices and algorithms that you don&#x27;t know exist, so it is able to do better - provided you know to ask and how to ask&#x2F;what to ask.

AI is trained on the same shitty code you&#x27;re inheriting, so probably not.

One thing that&#x27;s surprised me throughout my career is just how inefficient most of the code that I&#x27;ve inherited is. I suspect we could do a lot more with the hardware we have if we simply became better at programming.(Perhaps more AI coaching could help?)

It applies to any algorithm that can be implemented with a multitape Turing machine, which is still quite a few of them. The obliviousness requirement is only for random-access machines.

[ made this a top-level comment as I don&#x27;t see it mentioned in other comments: ]The result doesn&#x27;t actually apply to _all_ algorithms, only oblivious ones. Oblivious algorithms are ones where step i does not depend on decisions made in steps j &lt; i. Almost all useful algorithms are non-oblivious, with some notable exceptions [1]. This work is a step forward towards proving the result for the general case, with little practical usage (and that&#x27;s perfectly okay).[1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Sorting_network" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Sorting_network</a>

Related: <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=44212855">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=44212855</a> and <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=44055347">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=44055347</a>

Of course in many cases (such as the one you mentioned), the amount of memory needed does not grow with N. But there are other programs&#x2F;computation that seem to require more memory. For example, consider the following (Python) program:<pre><code> def intpow(n, r): return int(n**r)
 N = 10000
 a = [0] * N
 a[1] = 1
 for m in range(2, N):
 a[m] = a[m-1] + a[intpow(m, 0.6)] + a[intpow(m, 0.3)] + a[intpow(m, 0.1)]
 print(a[N-1])
</code></pre>
It populates an array of size N by, for each index m, accessing array elements at smaller values m-1, m^0.6, m^0.3 and m^0.1 (just arbitrary values I made up). So this is a program that runs in time about N, and as it can depend on array elements that go very far back, it may not be immediately obvious how to make it run with space significantly less than N^0.9 (say), let alone √N. But the result shows that it can be done (disclaimer: I haven&#x27;t actually verified the details of how the proof carries over to this program, but it looks like it should be possible), and for any program no matter how weird.

Sure, there are plenty of computations where you don&#x27;t need much space no matter how many times you loop--like if you&#x27;re just updating a single sum. But there are other problems where each time through the loop you might need to add an element to a big array or matrix, and then you go back and do more computation on the saved data elements to get the answer.Before this result, there were believed to be at least some problems where you need (almost) as much space as time, but Williams shows that, theoretically at least, that&#x27;s never necessarily the case.

I don&#x27;t understand what they are saying at all. If I have a computation that requires going through a loop n times, why should the memory requirements increase with n at all?

Thanks. I think the title is quite misleading then? I would have expected better from Scientific American.

Lower bound tells you how much it&#x27;s worth to improve the SOTA. It gives you a hint that you can do better.So it&#x27;s more like polar star. Maybe not directly practical, but it will lead tons of people in the right direction.

It&#x27;s a reduction from multitape Turing machine to tree evaluations. If your &quot;real algorithm&quot; is straightforwardly modeled by a multitape TM, then it might be possible to use this proof to reduce the space. Otherwise, I don&#x27;t think so.

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&#x27;s not an impossible problem. That will get people to build better stuff.

Upper bound on the space required. Anything, that is computable.&gt; 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.

&gt; Does it have any import on real algorithms?As-in algorithms you&#x27;ll care about if you&#x27;re a programmer and not overly interested in theory? Not really, no.

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?

Without paywall: <a href="https:&#x2F;&#x2F;www.removepaywall.com&#x2F;search?url=https:&#x2F;&#x2F;www.scientificamerican.com&#x2F;article&#x2F;new-proof-dramatically-compresses-space-needed-for-computation&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.removepaywall.com&#x2F;search?url=https:&#x2F;&#x2F;www.scienti...</a>

I think this means that while Log grows to infinity, it does that so slowly that it can often be treated as if it were a coefficient. Coefficients are ignored in big O notation, hence the negligibly small comment.

Maybe I&#x27;m missing context, but that sounds like O(n) or Ω(n).

In case someone doesn&#x27;t like the proof by example, here&#x27;s a hint: sqrt(t) = t &#x2F; sqrt(t).

t&#x2F;log(t) is &#x27;closer to&#x27; t than it is to sqrt(t) as t heads toward infinity.e.g:<pre><code> 4&#x2F;log2(4) = 4&#x2F;2 = 2
 sqrt(4) = 2

 2^32&#x2F;log2(2^32) = 2^32&#x2F;32 = 2^27
 sqrt(2^32) = 2^16</code></pre>

Here&#x27;s a quote from the SciAm article: &quot;Technically, that equation was t&#x2F;log(t), but for the numbers involved log(t) is typically negligibly small.&quot;Huh?

&gt;(Technically, that equation was t&#x2F;log(t), but for the numbers involved log(t) is typically negligibly small.)My dude, that is NOT how rational numbers work.

New proof dramatically compresses space needed for computation