Content deleted Content added
LouScheffer (talk | contribs) →Connectivity in undirected graphs: Add Low Density Parity Check Codes as an algorithm that was galactic when invented, but became practical later. |
LouScheffer (talk | contribs) →Possible use cases: Add explicit examples of each of the three use cases mentioned. |
||
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, 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 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:<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=http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf|doi=10.1145/1562164.1562186 |s2cid=5969255 }}</ref>
== Examples ==
| |||