zlacker

[return to "For algorithms, a little memory outweighs a lot of time"]
1. LPisGo+Y9[view] [source] 2025-05-21 20:27:55
>>makira+(OP)
I think it is very intuitive that more space beats the pants off of more time.

In time O(n) you can use O(n) cells on a tape, but there are O(2^n) possible configurations of symbols on a tape of length n (for an alphabet with 2 symbols), so you can do so much more with n space than with n time.

◧◩
2. IsTom+wc1[view] [source] 2025-05-22 08:27:18
>>LPisGo+Y9
One one hand yes, on the other there might be some problems that are inherently difficult to parallelize (alternating machine PTIME is the same as deterministic PSPACE) where space doesn't buy you much. The jump from paper from t/log t to sqrt(t log t) is huge, but it still might be that unbounded parallelism doesn't buy you much more.
[go to top]