←back to thread

190 points baruchel | 1 comments | | HN request time: 0.207s | source
Show context
kristianp ◴[] No.44421565[source]
This seems very theoretical, just a lower bound on space required, without talking about what is being computed. Does it have any import on real algorithms?
replies(6): >>44421590 #>>44421702 #>>44421728 #>>44422242 #>>44422376 #>>44422969 #
1. wasabi991011 ◴[] No.44422969[source]
It's a reduction from multitape Turing machine to tree evaluations. If your "real algorithm" is straightforwardly modeled by a multitape TM, then it might be possible to use this proof to reduce the space. Otherwise, I don't think so.