Talk:Computational complexity theory: Difference between revisions

Revision as of 19:49, 17 August 2007

Revision as of 03:02, 18 August 2007

Line 141:

:However, <s>not every algorithm is boundable with a Big-O limit (see [[run-time analysis]])</s> (''I might be wrong about that, too''), and there are undecidable algorithms (see [[halting problem]]). Unfortunately, I do not know if there are algorithms that are decidable for small inputs but undecidable for large inputs &ndash; but I can tell you that there are algorithms whose run-times grow extraordinarily rapidly as n increases, such that the fastest supercomputers in existence would take until the end of the universe to solve problems for sufficiently large inputs (see [[Ackermann function]] and [[busy beaver]] for examples). See [[Computational complexity theory#intractability|intractability]] for more info. [[User:Groupthink|Groupthink]] 00:03, 8 July 2007 (UTC)

== History ==

This page could use some history - in particular it ought to reference Juris Hartmanis and Richard Stearns' "On the Computational Complexity of Algorithms". It already cites a reference with some history. I can help with this. [[User:Dcoetzee|Dcoetzee]] 03:02, 18 August 2007 (UTC)