Galactic algorithm: Difference between revisions

Revision as of 15:34, 15 September 2022

Revision as of 19:13, 24 September 2022

Line 6:

* An algorithm, even if impractical, may show new techniques that may eventually be used to create practical algorithms.

* Available computational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical.

* 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. 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 provablyprobably 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 large but polynomial <math>O\bigl(n^{2^{100}}\bigr)</math> algorithm for the [[Boolean satisfiability problem]], 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 ==