Quasipolynomial-Time Algorithm

Definition

Quasipolynomial-Time Algorithm

An algorithm is quasipolynomial-time if there are constants $C>0$ and $d\ge 1$ such that its worst-case running time $T(n)$ satisfies, for every sufficiently large input size $n$,

$$T(n)\le 2^{C({\log }_{2}n{)}^d}=n^{C({\log }_{2}n{)}^{d-1}}.$$

This is commonly abbreviated as $T(n)=2^{(\log n{)}^{O(1)}}$. The case $d=1$ is polynomial time; bounds with $d>1$ may be superpolynomial but remain sub-exponential because $(\log n{)}^d=o(n)$.

Why it matters

Quasipolynomial time identifies an intermediate regime between polynomial and general exponential bounds:

$$n^{O(1)}\subseteq 2^{(\log n{)}^{O(1)}}\subseteq 2^{o(n)}.$$

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.