Definition
Quasipolynomial-Time Algorithm
An algorithm is quasipolynomial-time if there are constants
and such that its worst-case running time satisfies, for every sufficiently large input size , This is commonly abbreviated as
. The case is polynomial time; bounds with may be superpolynomial but remain sub-exponential because .
Why it matters
Quasipolynomial time identifies an intermediate regime between polynomial and general exponential bounds:
A quasipolynomial algorithm therefore gives a substantially stronger upper bound than exhaustive exponential search, even when no polynomial-time algorithm is known. A central example is the graph isomorphism problem: its quasipolynomial-time algorithm is major structural progress, but does not establish that graph isomorphism belongs to polynomial time.