Quasi-polynomial time

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 $c$ such that the worst-case running time of the algorithm, on inputs of size $n$, has an upper bound of the form $$2^{O((\log n{)}^c)}.$$

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.

Complexity class

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

$\mathsf{Q}\mathsf{P}=\bigcup _{c\in \mathbb{\mathbb{N}}}\mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}\left(2^{(\log n{)}^c}\right)$

Examples

An early example of a quasi-polynomial time algorithm was the Adleman–Pomerance–Rumely primality test.Template:R/superscript 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.Template:R/superscript

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:

• Finding the largest disjoint subset of a collection of unit disks in the hyperbolic plane can be solved in time $n^{O(\log n)}$, and requires time $n^{\mathrm{\Omega }(\log n)}$ under the exponential time hypothesis.Template:R/superscript
• Finding a graph with the fewest vertices that does not appear as an induced subgraph of a given graph can be solved in time $n^{O(\log n)}$, and requires time $n^{\mathrm{\Omega }(\log n)}$ under the exponential time hypothesis.Template:R/superscript
• Finding the smallest dominating set in a tournament. This is a subset of the vertices of the tournament that has at least one directed edge to all other vertices. It can be solved in time $n^{O(\log n)}$, and requires time $n^{\mathrm{\Omega }(\log n)}$ under the exponential time hypothesis.Template:R/superscript
• Computing the Vapnik–Chervonenkis dimension of a family of sets. This is the size of the largest set $S$ (not necessarily in the family) that is shattered by the family, meaning that each subset of $S$ can be formed by intersecting $S$ with a member of the family. It can be solved in time $n^{O(\log n)}$,Template:R/superscript and requires time $n^{(\log n{)}^{1/3-o(1)}}$ under the exponential time hypothesis.Template:R/superscript

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

• The planted clique problem, of determining whether a random graph has been modified by adding edges between all pairs of a subset of its vertices.Template:R/superscript
• Monotone dualization, several equivalent problems of converting logical formulas between conjunctive and disjunctive normal form, listing all minimal hitting sets of a family of sets, or listing all minimal set covers of a family of sets, with time complexity measured in the combined input and output size.Template:R/superscript
• Parity games, involving token-passing along the edges of a colored directed graph.Template:R/superscript The paper giving a quasi-polynomial algorithm for these games won the 2021 Nerode Prize.Template:R/superscript

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

• The graph isomorphism problem, determining whether two graphs can be made equal to each other by relabeling their vertices, announced in 2015 and updated in 2017 by László Babai.Template:R/superscript
• The unknotting problem, recognizing whether a knot diagram describes the unknot, announced by Marc Lackenby in 2021.Template:R/superscript

In approximation algorithms

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,Template:R/superscript finding the maximum clique on the intersection graph of disks,Template:R/superscript and determining the probability that a hypergraph becomes disconnected when some of its edges fail with given independent probabilities.Template:R/superscript

More strongly, the problem of finding an approximate Nash equilibrium has a QPTAS, but cannot have a PTAS under the exponential time hypothesis.Template:R/superscript