←back to thread

New proof dramatically compresses space needed for computation

(www.scientificamerican.com)
190 points baruchel | 1 comments | 27 Jun 25 13:59 UTC | HN request time: 0.207s | source
Show context
mikewarot ◴[30 Jun 25 10:58 UTC] No.44421746[source]▶
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.

replies(3): >>44423032 #>>44423353 #>>44423922 #
1. LegionMammal978 ◴[30 Jun 25 13:27 UTC] No.44423032[source]▶
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.

[0] https://arxiv.org/abs/2502.17779