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) 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."
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. These codes, though never used, inspired decades of research into more practical algorithms that today can achieve rates arbitrarily close to channel capacity.
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(n^2), 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 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) in
Knuth's up-arrow notation, where h is the number of vertices in H. 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 \uparrow \uparrow \uparrow 4 = {}^{65536}2 = \underbrace{2^{2^{\cdot^{\cdot^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 2^{126} operations. 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. 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".
Hutter search 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. 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. However, such a cooling schedule results in entirely impractical runtimes, and is never used. 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.
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. 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 and given the experimentally estimated implementation constants, it would only be faster than
Borůvka's algorithm for graphs in which m + n > 9 \cdot 10^{151}.
Hash tables Researchers have found an algorithm that achieves the provably best-possible asymptotic performance in terms of time-space tradeoff in
hash tables. 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." and "in practice, constants really matter. In the real world, a factor of 10 is a game ender.” providing an algorithm with asymptotically better space requirement. However,
the algorithm's very big constant hidden by the O(\text{log N}) means that on any realistic problem it consumes significantly more memory and computation time than the well known O(\text{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 at the
Massachusetts Institute of Technology in 1960. 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. 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, and became popular as a patent-free alternative. 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. == References ==