Editing Time complexity (section)

== Superpolynomial time ==
An algorithm is defined to take '''superpolynomial time''' if ''T''(''n'') is not bounded above by any polynomial; that is, if {{tmath|T(n)\not\in O(n^c)}} for every positive integer {{math|''c''}}.

For example, an algorithm that runs for {{math|2<sup>''n''</sup>}} steps on an input of size {{math|''n''}} requires superpolynomial time (more specifically, exponential time).

An algorithm that uses exponential resources is clearly superpolynomial, but some algorithms are only very weakly superpolynomial. For example, the [[Adleman–Pomerance–Rumely primality test]] runs for {{math|''n''<sup>''O''(log log ''n'')</sup>}} time on {{math|''n''}}-bit inputs; this grows faster than any polynomial for large enough {{math|''n''}}, but the input size must become impractically large before it cannot be dominated by a polynomial with small degree.

An algorithm that requires superpolynomial time lies outside the [[complexity class]] '''[[P (complexity)|P]]'''. [[Cobham's thesis]] posits that these algorithms are impractical, and in many cases they are. Since the [[P versus NP problem]] is unresolved, it is unknown whether [[NP-complete]] problems require superpolynomial time.