5 ms·
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?
by kristianp 1y ago
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?
- deleted 1y ago[deleted]
- wiz21c 1y agoLower bound tells you how much it's worth to improve the SOTA. It gives you a hint that you can do better. So it's more like polar star. Maybe not directly practical, but it will lead tons of people in the right direction.
- Gravityloss 1y agoThanks. I think the title is quite misleading then? I would have expected better from Scientific American.
- kadoban 1y ago> Does it have any import on real algorithms? As-in algorithms you'll care about if you're a programmer and not overly interested in theory? Not really, no.
- CommenterPerson 1y agoIt does have an impact. It wont give you stackoverflow like code to copy-paste though. Analogy is thermodynamics says how efficient a heat engine _could_ be. If your engine is way below that you know there how much of an improvement there _could_ be, that it's not an impossible problem. That will get people to build better stuff.
- bmacho 1y agoUpper bound on the space required. Anything, that is computable. > Does it have any import on real algorithms? It depends on the constants, but if the constants are good, you can have VMs for example that make memory usage smaller.
- wasabi991011 1y agoIt'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.