logoalt Hacker News

LegionMammal978yesterday at 1:27 PM0 repliesview on HN

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