Hacker News Reader

Comment by mhuffman | Hacker News Reader

They were likely the ones that invented the phrase.

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.

That's in practice for practical problems. But they were interested in the worst cases.

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.

The amount of steps is an (over)estimate on the amount of memory needed.

You can write some trivial programs that need this much memory. But most of them can be optimised to use less space (and still compute the same answer).

The big question was: can you always optimise the space usage down from the ridiculous maximum and to what extent?

But plenty of programs can only be optimized to take less space by making them run slower (i.e take more steps)...

Yes. But even with infinite time there's a limit to how much you can compress the space usage. And that's an interesting property to study.

In addition you can look at how much extra time you actually need: infinite time is a vast overestimate. The new proof gives much more reasonable time bounds.

That is also what is happening here. When you reduce space to sqrt you are increasing time complexity. The interesting part of the result is that you can make this tradeoff for _any_ problem.

> in a bunch of cases

That's precisely the issue: of course for many problems there are obvious ways to trade off space and time. Smart people who have spent their lives thinking about this are aware of this. :-) The issue here is: can this always be done? For an arbitrary computation that takes t time, can it always be simulated in much less space (using more time of course), no matter what the computation is? Lots of people have tried, and the best result until now was t/log t in the 1970s.

Edit: A comment on a previous discussion of this result by the author of the Quanta article, which substantiates and links to researchers' opinion that it's the universality (works for every problem) that's the surprising part: https://news.ycombinator.com/item?id=44075191

Reply on news.ycombinator.com