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 ${\displaystyle c}$ such that the worst-case running time of the algorithm, on inputs of size ${\displaystyle n}$, has an

$${\displaystyle 2^{O{\bigl (}(\log n)^{c}{\bigr )}}.}$$

The

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.^[1]

${\displaystyle {\mathsf {QP}}=\bigcup _{c\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{(\log n)^{c}}\right)}$

Examples

An early example of a quasi-polynomial time algorithm was the Adleman–Pomerance–Rumely primality test;^[2] 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.^[3]

In some cases, quasi-polynomial time bounds can be proven to be optimal under the

• 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.^[6]
• 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.^[7]
• Parity games, involving token-passing along the edges of a colored directed graph.^[8] The paper giving a quasi-polynomial algorithm for these games won the 2021 Nerode Prize.^[9]
• Computing the Vapnik–Chervonenkis dimension of a family of sets.^[10]
• Finding the smallest dominating set in a tournament, a subset of the vertices of the tournament that has at least one directed edge to all other vertices.^[11]

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.^[12]
• The
  knot diagram describes the unknot, announced by Marc Lackenby in 2021.^[13]

More strongly, the problem of finding an approximate Nash equilibrium has a QPTAS, but cannot have a PTAS under the exponential time hypothesis.^[16]

References