A '''galactic algorithm''' is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in practice. Galactic algorithms were so named by [[Richard Lipton]] and Ken Regan,<ref name="seminal">{{cite book |author=Lipton, Richard J., and Kenneth W. Regan |chapter=David Johnson: Galactic Algorithms |title=People, Problems, and Proofs |publisher=Springer Berlin |___location=Heidelberg |year=2013 |pages=109–112 |chapter-url=https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/}}</ref> as they will never be used on any of the merely terrestrial data sets on Earth.
== Possible use cases ==
Line 10:
== Examples ==
=== Integer multiplication ===
An example of a galactic algorithm is the fastest known way to [[multiplication algorithm|multiply two numbers]],<ref>{{Cite journal|last1=David|first1=Harvey|last2=Hoeven|first2=Joris van der|date=March 2019|title=Integer multiplication in time O(n log n)|url=https://hal.archives-ouvertes.fr/hal-02070778/document|journal=HAL|volume=hal-02070778}}</ref> which is based on a 1729-dimensional [[Fourier transform]].<ref name="quick">{{cite web |url=https://phys.org/news/2019-04-weve-quicker-big.html |title=We've found a quicker way to multiply really big numbers |author=David Harvey |date=April 2019 |publisher=Phys.org}}</ref> ThisIt meansneeds it will not reach its stated efficiency until the numbers have at least 2<supmath>1729<sup>12</sup></sup> bits O(atn least\log 10<sup>10<sup>38n)</sup></supmath> digits)bit operations, whichbut is vastly larger thanas the numberconstants ofhidden atoms inby the known[[big universe.O Sonotation]] thisare algorithmlarge, it is never used in practice.<ref name="conv">{{cite web |url=http://theconversation.com/weve-found-a-quicker-way-to-multiply-really-big-numbers-114923 |title=We've found a quicker way to multiply really big numbers}} Quote, from one of the authors of the algorithm: "The new algorithm is not really practical in its current form, because the proof given in our paper only works for ludicrously large numbers. Even if each digit was written on a hydrogen atom, there would not be nearly enough room available in the observable universe to write them down."</ref> However, it also shows why galactic algorithms may still be useful. One of theThe authors statesstate: "we are hopeful that with further refinements, the algorithm might become practical for numbers with merely billions or trillions of digits."<ref name="quick"/>
=== Matrix multiplication ===
The first improvement over brute-force matrix multiplication, which needs <math>O(n^3)</math> ismultiplications was the [[Strassen algorithm]],: a recursive algorithm that isneeds <math>O(n^{2.807})</math>multiplications. This algorithm is not galactic and is used in practice. Further extensions of this, using sophisticated group theory, are the [[Coppersmith–Winograd algorithm]] and its slightly better successors, deliveringneeding <math>O(n^{2.373})</math> multiplications. These are galactic – "We nevertheless stress that such improvements are only of theoretical interest, since the huge constants involved in the complexity of fast matrix multiplication usually make these algorithms impractical."<ref>{{citation
