Content deleted Content added
LouScheffer (talk | contribs) →Hutter search: Describe essence of Solomonoff induction, which involves averaging over all possible programs that reproduce existing data. |
|||
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 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 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 |
== Examples ==
| |||