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, because they will never be used on any data sets on Earth.
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: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 Θ ( n 2 100 ) {\displaystyle \Theta {\bigl (}n^{2^{100}}{\bigr )}} , 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.
Examples
Integer multiplication An example of a galactic algorithm is the fastest known way to multiply two numbers, which is based on a 1729-dimensional Fourier transform. It needs O ( n log n ) {\displaystyle O(n\log 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."
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 {\displaystyle <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 ( n 3 ) {\displaystyle O(n^{3})} operations) was the Strassen algorithm: a recursive algorithm that takes O ( n 2.807 ) {\displaystyle O(n^{2.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 ( n 2.373 ) {\displaystyle O(n^{2.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."
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 {\displaystyle n} -bit message, then decoding by finding the closest code word. If n {\displaystyle n} is chosen large enough, this beats any existing code and can get arbitrarily close to the capacity of the channel. Unfortunately, any n {\displaystyle n} big enough to beat existing codes is also completely impractical. These codes, though never used, inspired decades of research into more practical algorithms that today can achieve rates arbitrarily close to channel capacity.
… excerpt ends here. Continue reading the full article.
