Galactic algorithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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,[1] as they will never be used on any of the merely terrestrial data sets we find here on Earth.

Use cases[edit]

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.
  • Computer sizes may catch up to the crossover point, so that a previously impractical algorithm becomes practical.
  • 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. 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, an algorithm for the Boolean satisfiability problem, 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]

Examples[edit]

Integer multiplication[edit]

An example of a galactic algorithm is the fastest known way to multiply two numbers,[3] which is based on a 1729-dimensional Fourier transform.[4] This means it will not reach its stated efficiency until the numbers have at least 2172912 bits (at least 101038 digits), which is vastly larger than the number of atoms in the known universe. So this algorithm is never used in practice.[5] However, it also shows why galactic algorithms may still be useful. One of the authors states: "we are hopeful that with further refinements, the algorithm might become practical for numbers with merely billions or trillions of digits."[4]

Matrix multiplication[edit]

The first improvement over brute-force multiplication, is the Strassen algorithm, a recursive algorithm that is . 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, delivering . 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[edit]

Claude Shannon showed a simple but impractical code that could reach the capacity of a communication channel. It requires assigning a random code word to every possible -bit message, then decoding by finding the closest code word. If is chosen large enough, this beats any existing code and can get arbitrarily close to the capacity of the channel. Unfortunately, any 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[edit]

The problem of deciding whether a graph contains as a minor is NP-complete in general, but where is fixed, it can be solved in polynomial time. The running time for testing whether is a minor of in this case is ,[9] where is the number of vertices in and the big O notation hides a constant that depends superexponentially on . The constant is greater than in Knuth's up-arrow notation, where is the number of vertices in .[10] Even the case of cannot be reasonably computed as the constant is greater than with n = 65536. For , the constant is far larger: , where the part is an exponential stack of 16 copies of 2, a number so big its exact value cannot be practically computed.[11] The whole expression is a power tower of that many copies of 2.

Cryptographic breaks[edit]

For cryptographers, a cryptographic "break" is anything faster than a brute-force attack – i.e., performing one trial decryption for each possible key. In many cases, even though they are the best known methods, they are still infeasible with current technology. One example is the best attack known against 128-bit AES, which takes only operations.[12] Despite being impractical, theoretical breaks can sometimes provide insight into vulnerability patterns.

Traveling salesman problem[edit]

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 percent.[13] 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".[14]

Hutter search[edit]

A single algorithm, "Hutter search", can solve any well-defined problem in an asymptotically optimal time, barring some caveats. 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.[15][16] 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.

Optimization[edit]

Simulated annealing, when used with a logarithmic cooling schedule, has been proven to find the global optimum of any optimization problem. 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]

References[edit]

  1. ^ a b Lipton, Richard J., and Kenneth W. Regan (2013). "David Johnson: Galactic Algorithms". People, Problems, and Proofs. Heidelberg: Springer Berlin. pp. 109–112.{{cite book}}: CS1 maint: multiple names: authors list (link)
  2. ^ Fortnow, L. (2009). "The status of the P versus NP problem" (PDF). Communications of the ACM. 52 (9): 78–86. doi:10.1145/1562164.1562186. S2CID 5969255.
  3. ^ David, Harvey; Hoeven, Joris van der (March 2019). "Integer multiplication in time O(n log n)". HAL. hal-02070778.
  4. ^ a b David Harvey (April 2019). "We've found a quicker way to multiply really big numbers". Phys.org.
  5. ^ "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."
  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, arXiv:1204.1111, doi:10.1109/FOCS.2012.80, S2CID 2410545
  7. ^ Larry Hardesty (January 19, 2010). "Explained: The Shannon limit". MIT News Office.
  8. ^ "Capacity-Approaching Codes" (PDF).
  9. ^ Kawarabayashi, K. I.; Kobayashi, Y.; Reed, B. (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. CiteSeerX 10.1.1.114.3864. doi:10.1016/0196-6774(87)90043-5.
  11. ^ WolframAlpha computation
  12. ^ Biaoshuai Tao & Hongjun Wu (2015). Information Security and Privacy. Lecture Notes in Computer Science. Vol. 9144. pp. 39–56. doi:10.1007/978-3-319-19962-7_3. ISBN 978-3-319-19961-0.
  13. ^ Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (September 1, 2020). "A (Slightly) Improved Approximation Algorithm for Metric TSP". arXiv:2007.01409 [cs.DS].
  14. ^ Erica Klarreich (October 8, 2020). "Computer Scientists Break Traveling Salesperson Record".
  15. ^ Hutter, Marcus (2002-06-14). "The Fastest and Shortest Algorithm for All Well-Defined Problems". arXiv:cs/0206022.
  16. ^ Gagliolo, Matteo (2007-11-20). "Universal search". Scholarpedia. 2 (11): 2575. Bibcode:2007SchpJ...2.2575G. doi:10.4249/scholarpedia.2575. ISSN 1941-6016.
  17. ^ Liang, Faming, Yichen Cheng, and Guang Lin (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. S2CID 123410795.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  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.