Galactic algorithm: Difference between revisions

Revision as of 14:45, 22 July 2025

Latest revision as of 11:22, 29 July 2025

Line 4:

== 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, Lowlow-density parity-check codes, below.

* An impractical algorithm can still demonstrate that [[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 |first=Lance |year=2022 |title=Fifty Years of P Versus NP and the Possibility of the Impossible |url=https://dl.acm.org/doi/pdf/10.1145/3460351 |journal=Communications of the ACM |volume=65 |issue=1 |pages=76–85 |doi=10.1145/3460351 }}</ref>