Content deleted Content added
No edit summary |
No edit summary |
||
Line 9:
== Examples ==
There are several well-known algorithms with world-beating asymptotic behavior, but only on impractically large problems:
*Matrix multiplication: The first improvement over brute-force multiplication, O(''N''<sup>3</sup>) is the [[Strassen algorithm]], a recursive algorithm that is O(''N''<sup>2.807</sup>). This algorithm is not galactic and used in practice. Further extensions of this, using sophisticated group theory, are the [[Coppersmith–Winograd algorithm]] and its slightly better successors, delivering O(''N''<sup>2.373</sup>). These are galactic – "We nevertheless stress that such improvements are only of theoretical interest, since the huge constants involved in the complexity of fast matrix multiplication usually make these algorithms impractical."<ref>{{citation
| last = Le Gall | first = F.
| arxiv = 1204.1111
Line 17:
| title = Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012)
| year = 2012}}.</ref>
*The problem of [[decision problem|deciding]] whether a graph ''G'' contains ''H'' as a [[graph minor|minor]] is NP-complete in general, but where ''H'' is fixed, it can be solved in polynomial time. The running time for testing whether ''H'' is a minor of ''G'' in this case is ''O''(''n''<sup>2</sup>),<ref name="kkr12">{{harvtxt|Kawarabayashi|Kobayashi|Reed|2012}}.</ref> where ''n'' is the number of vertices in ''G'' and the [[big O notation]] hides a constant that depends superexponentially on ''H''. The constant is greater than (using [[Knuth's up-arrow notation]]), and where where ''h'' is the number of vertices in ''H'':<ref>{{cite journal |author=Johnson, David S. |title=The NP-completeness column: An ongoing guide (edition 19) |journal= Journal of algorithms |volume=8 |issue=2 |year=1987 |pages=285–303 |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.3864&rep=rep1&type=pdf}}</ref>
::<math> c > 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ). </math>
| |||