Galactic algorithm

Short description: Classification of algorithm

A galactic algorithm is an algorithm with record-breaking 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,[1] because they will never be used on any data sets on Earth.

## Contents

* 1 Possible use cases
* 2 Examples
* 2.1 Integer multiplication
* 2.2 Primality testing
* 2.3 Matrix multiplication
* 2.4 Communication channel capacity
* 2.5 Sub-graphs
* 2.6 Cryptographic breaks
* 2.7 Traveling salesman problem
* 2.8 Hutter search
* 2.9 Optimization
* 2.10 Minimum spanning trees
* 2.11 Hash tables
* 2.12 Connectivity in undirected graphs
* 2.13 Low-density parity-check codes
* 2.14 Polygon triangulation
* 3 References

## Possible use cases

Even if they are never used in practice, galactic algorithms may still contribute to computer science:

* An algorithm, even if impractical, may show new techniques that may eventually be used to create practical algorithms. See, for example, communication channel capacity, below.
* Available computational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical. See, for example, low-density parity-check codes, below.
* An impractical algorithm can still demonstrate that conjectured bounds can be achieved, or that proposed bounds are wrong, and hence advance the theory of algorithms (see, for example, Reingold's algorithm for connectivity in undirected graphs). As Lipton states:[1]

> This alone could be important and often is a great reason for finding such algorithms. For example, if tomorrow there were a discovery that showed there is a factoring algorithm with a huge but provably polynomial time bound, that would change our beliefs about factoring. The algorithm might never be used, but would certainly shape the future research into factoring.

Similarly, a hypothetical algorithm for the Boolean satisfiability problem with a large but polynomial time bound, such as Θ(n2100), although unusable in practice, would settle the P versus NP problem, considered the most important open problem in computer science and one of the Millennium Prize Problems.[2][3]

## Examples

### Integer multiplication

An example of a galactic algorithm is the fastest known way to multiply two numbers,[4] which is based on a 1729-dimensional Fourier transform.[5] It needs O(nlog⁡n) bit operations, but as the constants hidden by the big O notation are large, it is 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."[5]

### Primality testing

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 <10−100), good enough for practical purposes. There is also a deterministic version of the Miller-Rabin test, which runs in polynomial time over all inputs, but its correctness depends on the generalized Riemann hypothesis (which is widely believed, but not proven). The existence of these (much) faster alternatives means AKS is not used in practice.

### Matrix multiplication

The first improvement over brute-force matrix multiplication (which takes O(n3) operations) was the Strassen algorithm: a recursive algorithm that takes 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 O(n2.373) operations. 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."[6]

### Communication channel capacity

Claude Shannon showed a simple but asymptotically optimal code that can reach the theoretical capacity of a communication channel. It requires assigning a random code word to every possible n-bit message, then decoding by finding the closest code word. If n is chosen large enough, this beats any existing code and can get arbitrarily close to the capacity of the channel. Unfortunately, any n big enough to beat existing codes is also completely impractical.[7] These codes, though never used, inspired decades of research into more practical algorithms that today can achieve rates arbitrarily close to channel capacity.[8]

### Sub-graphs

The problem of deciding whether a graph G contains H as a minor is NP-complete in general, but where H is fixed, it can be solved in polynomial time. The running time for testing whether H is a minor of G in this case is O(n2),[9] where n is the number of vertices in G and the big O notation hides a constant that depends superexponentially on H. The constant is greater than 2↑↑(2↑↑(2↑↑(h/2))) in Knuth's up-arrow notation, where h is the number of vertices in H.[10] Even the case of h=4 cannot be reasonably computed as the constant is greater than 2 pentated by 4, or 2 tetrated by 65536, that is, 2↑↑↑4=655362=22⋅⋅2⏟65536.

### Cryptographic breaks

In cryptography jargon, a "break" is any attack faster in expectation than brute force – i.e., performing one trial decryption for each possible key. For many cryptographic systems, breaks are known, but are still practically infeasible with current technology. One example is the best attack known against 128-bit AES, which takes only 2126 operations.[11] Despite being impractical, theoretical breaks can provide insight into vulnerability patterns, and sometimes lead to discovery of exploitable breaks.

### Traveling salesman problem

For several decades, the best known approximation to the traveling salesman problem in a metric space was the very simple Christofides algorithm which produced a path at most 50% longer than the optimum. (Many other algorithms could usually do much better, but could not provably do so.) In 2020, a newer and much more complex algorithm was discovered that can beat this by 10−34 percent.[12] 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".[13]

### Hutter search

A single algorithm, "Hutter search", can solve any well-defined problem in an asymptotically optimal time, barring some caveats(Also see June 2025).. It works by searching through all possible algorithms (by runtime), while simultaneously searching through all possible proofs (by length of proof), looking for a proof of correctness for each algorithm. Since the proof of correctness is of finite size, it "only" adds a constant and does not affect the asymptotic runtime. However, this constant is so big that the algorithm is entirely impractical.[14][15] For example, if the shortest proof of correctness of a given algorithm is 1000 bits long, the search will examine at least 2999 other potential proofs first.

Hutter search is related to Solomonoff induction, which is a formalization of Bayesian inference. All computable theories (as implemented by programs) which perfectly describe previous observations are used to calculate the probability of the next observation, with more weight put on the shorter computable theories. Again, the search over all possible explanations makes this procedure galactic.

### Optimization

Simulated annealing, when used with a logarithmic cooling schedule, has been proven to find the global optimum of any optimization problem.[16] However, such a cooling schedule results in entirely impractical runtimes, and is never used.[17] However, knowing this ideal algorithm exists has led to practical variants that are able to find very good (though not provably optimal) solutions to complex optimization problems.[18][19]

### Minimum spanning trees

The expected linear time MST algorithm is able to discover the minimum spanning tree of a graph in O(m+n), where m is the number of edges and n is the number of nodes of the graph.[20] However, the constant factor that is hidden by the Big O notation is huge enough to make the algorithm impractical. An implementation is publicly available[21] and given the experimentally estimated implementation constants, it would only be faster than Borůvka's algorithm for graphs in which m+n>9⋅10151.[22]

### Hash tables

Researchers have found an algorithm that achieves the provably best-possible[23] asymptotic performance in terms of time-space tradeoff in hash tables.[24] But it remains purely theoretical: "Despite the new hash table’s unprecedented efficiency, no one is likely to try building it anytime soon. It’s just too complicated to construct."[25] and "in practice, constants really matter. In the real world, a factor of 10 is a game ender.”[25]

### Connectivity in undirected graphs

Connectivity in undirected graphs (also known as USTCON, for Undirected Source-Target CONnectivity) is the problem of deciding if a path exists between two nodes in an undirected graph, or in other words, if they are in the same connected component. When the usage of O(N) space is allowed, polynomial time solutions such as Dijkstra's algorithm have been known and used for decades. But for many years it was unknown if this could be done deterministically in O(log N) space (class L), though it was known to be possible with randomized algorithms (class RL).

A breakthrough 2008 paper by Omer Reingold showed that USTCON is in fact in L,[26] providing an algorithm with asymptotically better space requirement. However, the algorithm's very big constant hidden by the O(log N) means that on any realistic problem it consumes significantly more memory and computation time than the well known 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

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[27] at the Massachusetts Institute of Technology in 1960.[28][29] 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.[30]

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,[31] and became popular as a patent-free alternative.[32] 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

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.[33] However the proposed algorithm is extremely complex, and much simpler algorithms[34] with near-linear O(Nlog*N) performance are available, so these are used instead.[35] "His [Chazelle's] work represents an important theoretical breakthrough. However, his O(n) algorithm has appeared as very difficult to program and thus, to the knowledge of the authors, there is still no practical implementation available."[36]

## References

1. ↑ 1.0 1.1 Lipton, Richard J.; Regan, Kenneth W. (2013). "David Johnson: Galactic Algorithms". People, Problems, and Proofs: Essays from Gödel's Lost Letter: 2010. Heidelberg: Springer Berlin. pp. 109–112. ISBN 9783642414220. https://books.google.com/books?id=eLC9BAAAQBAJ&pg=PA109.
2. ↑ Fortnow, L. (2009). "The status of the P versus NP problem". Communications of the ACM 52 (9): 78–86. doi:10.1145/1562164.1562186. https://www.cs.cmu.edu/~15326-f23/CACM-Fortnow.pdf.
3. ↑ Fortnow, Lance (2022). "Fifty Years of P Versus NP and the Possibility of the Impossible". Communications of the ACM 65 (1): 76–85. doi:10.1145/3460351. https://dl.acm.org/doi/pdf/10.1145/3460351.
4. ↑ David, Harvey; Hoeven, Joris van der (March 2019). "Integer multiplication in time O(n log n)". HAL hal-02070778. https://hal.archives-ouvertes.fr/hal-02070778/document.
5. ↑ 5.0 5.1 Harvey, David (9 April 2019). "We've found a quicker way to multiply really big numbers" (in en). https://theconversation.com/weve-found-a-quicker-way-to-multiply-really-big-numbers-114923.
6. ↑ 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, doi:10.1109/FOCS.2012.80, ISBN 978-0-7695-4874-6
7. ↑ Larry Hardesty (January 19, 2010). "Explained: The Shannon limit". MIT News Office. https://news.mit.edu/2010/explained-shannon-0115.
8. ↑ "Capacity-approaching codes (Chapter 13 of Principles Of Digital Communication II)". MIT OpenCourseWare. 2005. https://ocw.mit.edu/courses/6-451-principles-of-digital-communication-ii-spring-2005/1a3ad00d83d1d042da3328a8edd9edc2_chap13.pdf.
9. ↑ 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.
10. ↑ Johnson, David S. (1987). "The NP-completeness column: An ongoing guide (edition 19)". Journal of Algorithms 8 (2): 285–303. doi:10.1016/0196-6774(87)90043-5.
11. ↑ Biaoshuai Tao; Hongjun Wu (2015). Information Security and Privacy. Lecture Notes in Computer Science. 9144. pp. 39–56. doi:10.1007/978-3-319-19962-7_3. ISBN 978-3-319-19961-0.
12. ↑ Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (September 1, 2020). "A (Slightly) Improved Approximation Algorithm for Metric TSP". arXiv:2007.01409 [cs.DS].
13. ↑ Klarreich, Erica (8 October 2020). "Computer Scientists Break Traveling Salesperson Record". https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/.
14. ↑ Hutter, Marcus (2002-06-14). "The Fastest and Shortest Algorithm for All Well-Defined Problems". arXiv:cs/0206022.
15. ↑ Gagliolo, Matteo (2007-11-20). "Universal search" (in en). Scholarpedia 2 (11): 2575. doi:10.4249/scholarpedia.2575. ISSN 1941-6016. Bibcode: 2007SchpJ...2.2575G.
16. ↑ Granville, V.; Krivanek, M.; Rasson, J.-P. (1994). "Simulated annealing: A proof of convergence". IEEE Transactions on Pattern Analysis and Machine Intelligence 16 (6): 652–656. doi:10.1109/34.295910. Bibcode: 1994ITPAM..16..652G.
17. ↑ Nolte, Andreas; Schrader, Rainer (1997), "A Note on the Finite Time Behaviour of Simulated Annealing", Operations Research Proceedings 1996 (Berlin, Heidelberg: Springer Berlin Heidelberg) 1996: pp. 175–180, doi:10.1007/978-3-642-60744-8_32, ISBN 978-3-540-62630-5, http://link.springer.com/10.1007/978-3-642-60744-8_32, retrieved 2023-02-06
18. ↑ Ingber, Lester (1993). "Simulated annealing: Practice versus theory". Mathematical and Computer Modelling 18 (11): 29–57. doi:10.1016/0895-7177(93)90204-C.
19. ↑ Liang, Faming; Cheng, Yichen; Lin, Guang (2014). "Simulated stochastic approximation annealing for global optimization with a square-root cooling schedule". Journal of the American Statistical Association 109 (506): 847–863. doi:10.1080/01621459.2013.872993.
20. ↑ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995-03-01). "A randomized linear-time algorithm to find minimum spanning trees". Journal of the ACM 42 (2): 321–328. doi:10.1145/201019.201022. ISSN 0004-5411.
21. ↑ 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)". https://github.com/FranciscoThiesen/karger-klein-tarjan.
22. ↑ Geiman Thiesen, Francisco. "Expected Linear-Time Minimum Spanning Trees". https://franciscothiesen.github.io/Linear-Time-MST/.
23. ↑ Li, Tianxiao; Liang, Jingxun; Yu, Huacheng; Zhou, Renfei (6 November 2023). "2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)". IEEE. pp. 1842–1862. doi:10.1109/FOCS57990.2023.00112. ISBN 979-8-3503-1894-4.
24. ↑ 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].
25. ↑ 25.0 25.1 Nadis, Steve (8 February 2024). "Scientists Find Optimal Balance of Data Storage and Time". https://www.quantamagazine.org/scientists-find-optimal-balance-of-data-storage-and-time-20240208/.
26. ↑ "Undirected connectivity in log-space", Journal of the ACM 55 (4): 1–24, 2008, doi:10.1145/1391289.1391291 .
27. ↑ Gallager, Robert G. (1960). Low density parity check codes (PDF) (Ph.D thesis). Massachusetts Institute of Technology.
28. ↑ Hardesty, L. (January 21, 2010). "Explained: Gallager codes". MIT News. http://web.mit.edu/newsoffice/2010/gallager-codes-0121.html.
29. ↑ Gallager, R.G. (January 1962). "Low density parity check codes". IRE Trans. Inf. Theory 8 (1): 21–28. doi:10.1109/TIT.1962.1057683. Bibcode: 1962IRTIT...8...21G.
30. ↑ 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". Proceedings of the IEEE (IEEE) 95 (11): 2142–2156. doi:10.1109/JPROC.2007.905132. http://coding.jpl.nasa.gov/~hamkins/publications/journals/2007_11_turbo_LDPC.pdf. Retrieved 2025-03-04.
31. ↑ "Near Shannon limit performance of low density parity check codes". Electronics Letters (IET) 32 (18): 1645–1646. 1996. doi:10.1049/el:19961141. Bibcode: 1996ElL....32.1645M. https://docs.switzernet.com/people/emin-gabrielyan/060708-thesis-ref/papers/MacKay96.pdf.
32. ↑ Erico Guizzo (Mar 1, 2004). "CLOSING IN ON THE PERFECT CODE". IEEE Spectrum. https://spectrum.ieee.org/closing-in-on-the-perfect-code. "Another advantage, perhaps the biggest of all, is that the LDPC patents have expired, so companies can use them without having to pay for intellectual-property rights."
33. ↑ "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry 6 (3): 485–524, 1991, doi:10.1007/BF02574703, ISSN 0179-5376
34. ↑ Seidel, Raimund (1991). "A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons". Computational Geometry 1 (1): 51–64. doi:10.1016/0925-7721(91)90012-4.
35. ↑ Žalik, Borut; Lamot, Marko (2000). "A contribution to triangulation algorithms for simple polygons". Journal of Computing and Information Technology 8 (4): 319–331. doi:10.2498/cit.2000.04.07.
36. ↑ 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.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Galactic algorithm. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Galactic_algorithm&oldid=4346736"