4 ms·
Galactic Algorithms (2010)
- tectonic 7y agoFrom the article: "A galactic algorithm is an algorithm that is wonderful in its asymptotic behavior, but is never used to actual compute anything."
- phomer 7y agoYes. Theoretically the algorithm is tractable, but the exponent is so large that it wouldn't be practical to run it in a real environment.
- amelius 7y agoAccording to the article, the algorithm does not need to have a polynomial bound to be classified as "galactic".
- phomer 7y agoIt is mentioned a couple times explicitly, but I think most of the readers for this blog would know that the border line for tractable is polynomial growth. Still, it is an interesting observation, worth investigating.
- kevinventullo 7y agoA somewhat famous, more recent example: https://news.ycombinator.com/item?id=19474280 https://news.ycombinator.com/item?id=19474280
- BeetleB 7y agoIn lay terms, an example of a galactic algorithm is one which has better big O complexity than algorithms currently in use, but where the crossover point of better performance than the status quo requires an incredibly large N - so large that we can't conceive any practical problem where this algorithm will perform better. For example, you may need an N larger than the number of stars in the universe. Hence the term "galactic". I've seen another one that requires an N larger than the number of atoms in the universe.
- voidmain 7y agoThe Fastest and Shortest Algorithm for All Well-Defined Problems [1] An algorithm M is described that solves any well-defined problem p as quickly as the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms. (The constants in the "low order" terms are... large. Basically this is a delightful reductio of asymptotic analysis) [1] https://arxiv.org/abs/cs/0206022 https://arxiv.org/abs/cs/0206022