Content deleted Content added
LouScheffer (talk | contribs) →Low Density Parity Check codes: Add link to thesis where these codes were first developed. |
fixed broken pdf link, also added newer survey from the same author (2021 vs 2009) |
||
Line 6:
* 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=
== Examples ==
| |||