2 ms·
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
by eru 1y ago
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?
- mort96 1y agoBut plenty of programs can only be optimized to take less space by making them run slower (i.e take more steps)...
- eru 1y agoYes. 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.
- Ar-Curunir 1y agoThat 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.