An algorithm is said to take superpolynomial time if T(n) is not bounded above by any polynomial. It is ω(nc) time for all constants c, where n is the input parameter, typically the number of bits in the input.
For example, an algorithm that runs for 2n steps on an input of size 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 nO(log log n) time on n-bit inputs; this grows faster than any polynomial for large enough n, but the input size must become impractically large before it cannot be dominated by a polynomial with small degree.
An algorithm that has been proven to require superpolynomial time cannot be solved in polynomial time, and so is known to lie outside the complexity class P. Cobham's thesis conjectures that these algorithms are impractical, and in many cases they are. Since the P versus NP problem is unresolved, no algorithm for a NP-complete problem is currently known to run in polynomial time.
Read more about this topic: Time Complexity
Famous quotes containing the word time:
“To be faced with what so-and-so’s mother lets him do, or what the teacher said in class today or what all the kids are wearing is to be required to reexamine some part of our belief structure. Each time we rethink our values we reaffirm them or begin to change them. Seen in this way, parenthood affords us an exceptional opportunity for growth.”
—Ruth Davidson Bell (20th century)