zlacker
[return to "For algorithms, a little memory outweighs a lot of time"]
◧
1. cperci+r9
[view]
[source]
2025-05-21 20:24:10
>>makira+(OP)
Minus the fuzz: A multitape Turing machine running in time
t
can be simulated using
O(sqrt(t log t))
space (and typically more than
t
time).
https://arxiv.org/abs/2502.17779
◧◩
2. diamon+Ej1
[view]
[source]
2025-05-22 09:41:33
>>cperci+r9
Should have come to the comments first!
[go to top]