In computational complexity theory and the analysis of algorithms, an algorithm is said to take quasi-polynomial time if its time complexity is quasi-polynomially bounded. That is, there should exist a constant ${\displaystyle c}$ such that the worst-case running time of the algorithm, on inputs of size ${\displaystyle n}$, has an upper bound of the form $${\displaystyle 2^{O{\bigl (}(\log n)^{c}{\bigr )}}.}$$

The decision problems with quasi-polynomial time algorithms are natural candidates for being NP-intermediate, neither having polynomial time nor likely to be NP-hard.

The complexity class QP consists of all problems that have quasi-polynomial time algorithms. It can be defined in terms of DTIME as follows.

An early example of a quasi-polynomial time algorithm was the Adleman–Pomerance–Rumely primality test. However, the problem of testing whether a number is a prime number has subsequently been shown to have a polynomial time algorithm, the AKS primality test.

In some cases, quasi-polynomial time bounds can be proven to be optimal under the exponential time hypothesis or a related computational hardness assumption. For instance, this is true for the following problems:

Other problems for which the best known algorithm takes quasi-polynomial time include:

Problems for which a quasi-polynomial time algorithm has been announced but not fully published include:

Quasi-polynomial time has also been used to study approximation algorithms. In particular, a quasi-polynomial-time approximation scheme (QPTAS) is a variant of a polynomial-time approximation scheme whose running time is quasi-polynomial rather than polynomial. Problems with a QPTAS include minimum-weight triangulation, finding the maximum clique on the intersection graph of disks, and determining the probability that a hypergraph becomes disconnected when some of its edges fail with given independent probabilities.