Superpolynomial time describes any algorithm whose number of steps grows faster than any polynomial function of the input size. If polynomial time means an algorithm’s steps stay within bounds like n², n³, or n¹⁰, superpolynomial time is everything beyond that: the point where adding a little more input causes the workload to explode in ways no fixed-exponent polynomial can capture.
How Growth Rates Compare
To understand superpolynomial time, it helps to see where it sits relative to the two categories most people learn first: polynomial and exponential.
Polynomial time covers any running time that doesn’t increase faster than n^k, where k is some fixed constant. This includes constant time, logarithmic time, linear time (n), quadratic time (n²), cubic time (n³), and so on. These algorithms are generally considered “fast” or “tractable” in computer science, and the complexity class P is defined as the set of all problems solvable in polynomial time.
Superpolynomial time is the complement: any running time that does increase faster than n^k for every fixed k. This includes exponential time (2^n), factorial time (n!), and many functions in between. A concise way to state it: a function is superpolynomial if it grows faster than every power of n, no matter how large the exponent.
The practical difference is dramatic. An n³ algorithm processing an input of size 100 takes about a million steps. A 2^n algorithm on the same input takes roughly 10³⁰ steps, a number so large that no computer on Earth could finish before the heat death of the universe. That gap is exactly why the polynomial/superpolynomial boundary matters so much in computer science.
Not All Superpolynomial Time Is Exponential
One common misconception is that “superpolynomial” and “exponential” mean the same thing. They don’t. Exponential time (like 2^n or 10^n) is superpolynomial, but there are superpolynomial functions that grow slower than any exponential. These occupy a middle zone sometimes called subexponential time.
A good example is the function 2^(√n). For any polynomial n^k, this eventually outgrows it, so it’s superpolynomial. But it also grows much slower than 2^n, because the exponent is √n rather than n itself. Functions like n^(log n) fall into the same gap: faster than any polynomial, slower than any exponential.
This middle zone isn’t just a mathematical curiosity. Some of the most important algorithms in cryptography live there. The best known classical method for factoring large integers, the General Number Field Sieve, runs in time roughly exp(c · (log n)^(1/3) · (log log n)^(2/3)), where c is a constant. That’s superpolynomial (it outpaces every polynomial) but subexponential (it’s far slower than 2^n). This is why RSA encryption works: factoring your key isn’t polynomial-time easy, but it’s not brute-force exponential either. It sits in the uncomfortable middle, slow enough to be secure for practical key sizes.
Why the Boundary Matters in Complexity Theory
The polynomial/superpolynomial divide is the central fault line in computational complexity. The class P contains every problem solvable in polynomial time. The class EXP contains problems requiring exponential time. It’s been formally proven that P is strictly smaller than EXP, meaning some problems genuinely require superpolynomial effort.
The most famous open question in computer science, whether P equals NP, is essentially asking whether a huge collection of important problems require superpolynomial time or not. NP is the class of problems where a proposed solution can be checked quickly (in polynomial time), even if finding that solution from scratch seems to require brute-force search. Every known algorithm for NP-complete problems like the traveling salesman problem or Boolean satisfiability runs in superpolynomial time. But no one has proven that faster algorithms can’t exist. If P ≠ NP (as most researchers believe), it would mean these problems are inherently superpolynomial, and no clever shortcut will ever bring them into polynomial territory.
Superpolynomial Speedups From Quantum Computing
Quantum computers are interesting in this context because they can, for certain problems, collapse superpolynomial classical running times down to polynomial. The most famous example is Shor’s algorithm for integer factoring. Classical computers need the subexponential (but still superpolynomial) General Number Field Sieve. A quantum computer running Shor’s algorithm factors the same number in polynomial time, a superpolynomial speedup.
Recent research published in Science Advances has extended this idea beyond factoring. By building on Shor’s algorithm, researchers constructed a proof that fault-tolerant quantum computers can approximate certain combinatorial optimization problems, like variants of integer programming, superpolynomially faster than any classical algorithm. The classical hardness in these cases traces back to the difficulty of inverting RSA encryption, which itself relies on the superpolynomial cost of factoring. A quantum computer sidesteps that cost entirely.
This doesn’t mean quantum computers make all superpolynomial problems easy. The speedup applies to specific problem structures. But it illustrates that the superpolynomial barrier isn’t always a fixed wall. It can depend on what kind of machine you’re running.
Recognizing Superpolynomial Functions
If you’re trying to determine whether a given function is superpolynomial, the test is straightforward: does it eventually outgrow n^k for every constant k? Here are common examples on each side.
- Polynomial (not superpolynomial): n, n², n¹⁰⁰, 5n³ + 2n, log n
- Superpolynomial but subexponential: n^(log n), 2^(√n), 2^((log n)²)
- Superpolynomial and exponential: 2^n, 10^n, 3^(2n)
- Superpolynomial and worse than exponential: n!, n^n, 2^(n²)
The key intuition is that polynomial functions have a fixed exponent applied to the input, while superpolynomial functions have the input (or something growing with the input) appearing in the exponent, the factorial, or some other position that makes growth accelerate without bound. A function like n¹⁰⁰ is technically polynomial, even though it grows very fast for small inputs, because 100 is a fixed constant. Meanwhile, n^(log n) is superpolynomial because the exponent (log n) keeps increasing as n grows, eventually surpassing any fixed value.