🔗 Galactic Algorithm

A galactic algorithm is one that runs faster than 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, as they will never be used on any of the merely terrestrial data sets we find here on Earth.

An example of a galactic algorithm is the fastest known way to multiply two numbers, which is based on a 1729-dimensional Fourier transform. This means it will not reach its stated efficiency until the numbers have at least 2¹⁷²⁹¹² bits (at least 10¹⁰³⁸ digits), which is vastly larger than the number of atoms in the known universe. So this algorithm is never used in practice.

Despite the fact that they will never be used, 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 alternatively show that conjectured bounds are wrong. As Lipton says "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 ${\displaystyle O\left(n^{2^{100}}\right)}$ algorithm for the Boolean satisfiability problem, although unusable in practice, would settle the P versus NP problem, the most important open problem in computer science and one of the Millennium Prize Problems.