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 such that the worst-case running time of the algorithm, on inputs of has an upper bound of the form
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.

Examples

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:
  • Finding the largest disjoint subset of a collection of unit disks in the hyperbolic plane can be solved in time, and requires time under the exponential time hypothesis.
  • Finding a graph with the fewest vertices that does not appear as an induced subgraph of a given graph can be solved in time, and requires time under the exponential time hypothesis.
  • 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, and requires time under the exponential time hypothesis.
  • Computing the Vapnik–Chervonenkis dimension of a family of sets. This is the size of the largest set that is shattered by the family, meaning that each subset of can be formed by intersecting with a member of the family. It can be solved in time, and requires time under the exponential time hypothesis.
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.
  • 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.
  • Parity games, involving token-passing along the edges of a colored directed graph. The paper giving a quasi-polynomial algorithm for these games won the 2021 Nerode Prize.
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 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.
More strongly, the problem of finding an approximate Nash equilibrium has a QPTAS, but cannot have a PTAS under the exponential time hypothesis.