Galactic algorithm: Difference between revisions

Revision as of 08:28, 16 March 2025

Revision as of 18:05, 19 March 2025

Line 3:

== 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, optimization by simulated annealing, 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[[conjecture]]d 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 (graph theory)|connectivity]] in undirected graphs.) As Lipton states:<ref name="seminal"/>{{quote |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 <math>\Theta\bigl(n^{2^{100}}\bigr)</math>, 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]].<ref>{{cite journal |author=Fortnow, L. |year=2009 |title=The status of the P versus NP problem |journal=Communications of the ACM |volume=52 |issue=9 |pages=78–86 |url=https://www.cs.cmu.edu/~15326-f23/CACM-Fortnow.pdf|doi=10.1145/1562164.1562186 |s2cid=5969255 }}</ref><ref>{{cite journal |author=Fortnow, L. |year=2021 |title=Fifty Years of P Versus NP and the Possibility of the Impossible |journal=Proceedings of ACM Conference (Conference’17) |url=https://lance.fortnow.com/papers/files/pvnp50.pdf }}</ref>

== Examples ==

Line 13:

=== 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 number|prime]]. In particular, 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. [[Elliptic curve primality proving|ECPP]] in practice runs much faster than AKS, but it has never been proven to be polynomial time. The [[Miller–Rabin primality test|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 <math>< 10^{-100}</math>), good enough for practical purposes. There is also a [[Miller–Rabin primality test#Deterministic variants|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 needs <math>O(n^3)</math> multiplications) was the [[Strassen algorithm]]: a recursive algorithm that needs <math>O(n^{2.807})</math> 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 <math>O(n^{2.373})</math> 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."<ref>{{citation

| last = Le Gall | first = F.

| arxiv = 1204.1111

Line 40:

=== 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 [[formal proof|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.<ref>{{cite arXiv|last=Hutter|first=Marcus|date=2002-06-14|title=The Fastest and Shortest Algorithm for All Well-Defined Problems|eprint=cs/0206022}}</ref><ref>{{Cite journal|last=Gagliolo|first=Matteo|date=2007-11-20|title=Universal search|journal=Scholarpedia|language=en|volume=2|issue=11|pages=2575|doi=10.4249/scholarpedia.2575|issn=1941-6016|bibcode=2007SchpJ...2.2575G|doi-access=free}}</ref> 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.

Hutter search is related to [[Solomonoff's theory of inductive inference|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.<ref>{{cite journal |last1=Liang |first1=Faming |first2=Yichen |last2=Cheng |first3=Guang |last3=Lin |title=Simulated stochastic approximation annealing for global optimization with a square-root cooling schedule |journal=Journal of the American Statistical Association |volume=109 |issue=506 |year=2014 |pages=847–863|doi=10.1080/01621459.2013.872993 |s2cid=123410795 }}</ref> 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.<ref>{{cite journal |author= Ingber, Lester |title=Simulated annealing: Practice versus theory |journal=Mathematical and Computer Modelling |volume=18 |issue=11 |year=1993 |pages=29–57|doi=10.1016/0895-7177(93)90204-C |doi-access=free |citeseerx=10.1.1.15.1046 }}</ref>

=== Minimum spanning trees ===