Galactic algorithm

A galactic algorithm is an algorithm with state-of-the-art theoretical (asymptotic) performance, but which is not used due to practical constraints. Typical reasons are that the performance gains only appear for problems that are so large they never occur, or the algorithm's complexity outweighs a relatively small gain in real-world performance. Galactic algorithms were so named by Richard Lipton and Ken Regan, because they will never be used on any data sets on Earth.

O(nlog⁡n) bit operations, but as the constants hidden by the big O notation are large, it is almost never used in practice. However, it also shows why galactic algorithms may still be useful. The authors state: "we are hopeful that with further refinements, the algorithm might become practical for numbers with merely billions or trillions of digits."

The AKS primality test is galactic. It is the most theoretically sound of any known algorithm that can take an arbitrary number and tell if it is prime. In particular, it is provably polynomial-time, deterministic, and unconditionally correct. All other known algorithms fall short on at least one of these criteria, but the shortcomings are minor and the calculations are much faster, so they are used instead. ECPP in practice runs much faster than AKS, but it has never been proven to be polynomial time. The Miller–Rabin test is also much faster than AKS, but produces only a probabilistic result. However the probability of error can be driven down to arbitrarily small values (say O(n2.807) operations. 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, taking n is chosen large enough, this beats any existing code and can get arbitrarily close to the capacity of the channel. Unfortunately, any H as a minor is NP-complete in general, but where G in this case is G and the big O notation hides a constant that depends superexponentially on h=4 cannot be reasonably computed as the constant is greater than 2 pentated by 4, or 2 tetrated by 65536, that is, 10−34 percent. Although no one will ever switch to this algorithm for its very slight worst-case improvement, it is still considered important because "this minuscule improvement breaks through both a theoretical logjam and a psychological one".

A single algorithm, "Hutter search", can solve any well-defined problem in an asymptotically optimal time, barring some caveats.m is the number of edges and O(N) space is allowed, almost-linear time solutions using disjoint-set data structures have been known and used for decades. But for many years it was unknown if this could be done deterministically in O(N) algorithms. Despite not being used in practice, the paper is still a landmark in theory, and has been cited more than 1000 times as of 2026.

Low-density parity-check codes, also known as LDPC or Gallager codes, are an example of an algorithm that was galactic when first developed, but became practical as computation improved. They were originally conceived by Robert G. Gallager in his doctoral dissertation at the Massachusetts Institute of Technology in 1960. Although their performance was much better than other codes of that time, reaching the Gilbert–Varshamov bound for linear codes, the codes were largely ignored as their iterative decoding algorithm was prohibitively computationally expensive for the hardware available.

Renewed interest in LDPC codes emerged following the invention of the closely related turbo codes (1993), whose similarly iterative decoding algorithm outperformed other codes used at that time. LDPC codes were subsequently rediscovered in 1996, and became popular as a patent-free alternative. Even though the turbo code patents have now expired, LDPC codes also have some technical advantages, and are used in many applications today.

Polygon triangulation is the division of a polygon into non-overlapping triangles. Bernard Chazelle showed in 1991 that any simple polygon can be triangulated in linear time. However the proposed algorithm is extremely complex, and much simpler algorithms with near-linear

1. ↑ As of October 2026, OpenAI has proposed a very slightly faster method with claimed complexity Harvey, David; van der Hoeven, Joris (March 2019). "Integer multiplication in time O(n log n)". HAL. hal-02070778.
2. 1 2 Le Gall, F. (2012), "Faster algorithms for rectangular matrix multiplication", Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pp. 514–523, arXiv:1204.1111, doi:10.1109/FOCS.2012.80, ISBN 978-0-7695-4874-6, S2CID 2410545
3. ↑ Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Reed, Bruce (2012). "The disjoint paths problem in quadratic time". Journal of Combinatorial Theory. Series B. 102 (2): 424–435. doi:10.1016/j.jctb.2011.07.004.
4. ↑ Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (September 1, 2020). "A (Slightly) Improved Approximation Algorithm for Metric TSP". arXiv:2007.01409 [cs.DS].
5. ↑ Gagliolo, Matteo (2007-11-20). "Universal search". Scholarpedia. 2 (11): 2575. Bibcode:2007SchpJ...2.2575G. doi:10.4249/scholarpedia.2575. ISSN 1941-6016.
6. ↑ Ingber, Lester (1993). "Simulated annealing: Practice versus theory". Mathematical and Computer Modelling. 18 (11): 29–57. CiteSeerX 10.1.1.15.1046. doi:10.1016/0895-7177(93)90204-C.{{cite journal}}: Cite uses deprecated parameter |citeseerx= (help)
7. ↑ Thiesen, Francisco. "A C++ implementation for an Expected Linear-Time Minimum Spanning Tree Algorithm(Karger-Klein-Tarjan + Hagerup Minimum Spanning Tree Verification as a sub-routine)". GitHub. Retrieved 2022-11-19.
8. ↑ Bender, Michael; Farach-Colton, Martin; Kuszmaul, John; Kuszmaul, William; Mingmou, Liu (4 Nov 2021). "On the Optimal Time/Space Tradeoff for Hash Tables". arXiv:2111.00602 [cs].
9. 1 2 Gallager, Robert G. (1960). Low density parity check codes (PDF) (Ph.D thesis). Massachusetts Institute of Technology.
10. ↑ Andrews, Kenneth S; Divsalar, Dariush; Dolinar, Sam; Hamkins, Jon; Jones, Christopher R; Pollara, Fabrizio (2007). "The development of turbo and LDPC codes for deep-space applications" (PDF). Proceedings of the IEEE. 95 (11). IEEE: 2142–2156. doi:10.1109/JPROC.2007.905132. Archived from the original on 2009-06-20. Retrieved 2025-03-04.{{cite journal}}: CS1 maint: bot: original URL status unknown (link)
11. ↑ Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 6 (3): 485–524, doi:10.1007/BF02574703, ISSN 0179-5376
12. ↑ Lamot, Marko; Žalik, Borut (2003). "A fast polygon triangulation algorithm based on uniform plane subdivision". Computers & Graphics. 27 (2): 239–253. doi:10.1016/S0097-8493(02)00281-9.