Galactic algorithm

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] It needs ${\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."[4]

The first improvement over brute-force matrix multiplication (which needs ${\displaystyle O(n^{3})}$ multiplications) was the Strassen algorithm: a recursive algorithm that needs ${\displaystyle O(n^{2.807})}$multiplications. 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, needing ${\displaystyle O(n^{2.373})}$ multiplications. 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."[5]

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 ${\displaystyle n}$-bit message, then decoding by finding the closest code word. If ${\displaystyle n}$ is chosen large enough, this beats any existing code and can get arbitrarily close to the capacity of the channel. Unfortunately, any ${\displaystyle n}$ big enough to beat existing codes is also completely impractical.[6] These codes, though never used, inspired decades of research into more practical algorithms that today can achieve rates arbitrarily close to channel capacity.[7]

The problem of deciding whether a graph ${\displaystyle G}$ contains ${\displaystyle H}$ as a minor is NP-complete in general, but where ${\displaystyle H}$ is fixed, it can be solved in polynomial time. The running time for testing whether ${\displaystyle H}$ is a minor of ${\displaystyle G}$ in this case is ${\displaystyle O(n^{2})}$,[8] where ${\displaystyle n}$ is the number of vertices in ${\displaystyle G}$ and the big O notation hides a constant that depends superexponentially on ${\displaystyle H}$. The constant is greater than ${\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}$ in Knuth's up-arrow notation, where ${\displaystyle h}$ is the number of vertices in ${\displaystyle H}$.[9] Even the case of ${\displaystyle h=4}$ cannot be reasonably computed as the constant is greater than ${\displaystyle {\ \atop {\ }}{{\underbrace {2^{2^{\cdot ^{\cdot ^{2}}}}} } \atop n}}$ with n = 65536.

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 ${\displaystyle 2^{126}}$ operations.[10] Despite being impractical, theoretical breaks can sometimes provide insight into vulnerability patterns.

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 ${\displaystyle 10^{-34}}$ percent.[11] 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".[12]

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.[13][14] For example, if the shortest proof of correctness of a given algorithm is 1000 bits long, the search will examine at least 2⁹⁹⁹ other potential proofs first.

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.[15] 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.[16]

The expected linear time MST algorithm is able to discover the Minimum spanning tree of a graph in ${\displaystyle O(m+n)}$, where ${\displaystyle m}$ is the number of edges and ${\displaystyle n}$ is the number of nodes of the graph.[17] 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[18] and given the experimentally estimated implementation constants, it would only be faster than Borůvka's algorithm for graphs in which ${\displaystyle m+n>9\cdot 10^{151}}$.[19]