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 {{nowrap|size $n$ ,}} has an upper bound of the form

$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.

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.{{r|zoo}}

: $\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.{{r|apr}} 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.{{r|aks}}

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^{\Omega(\log n)}$ under the exponential time hypothesis.{{r|hyperind}}
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^{\Omega(\log n)}$ under the exponential time hypothesis.{{r|missing}}
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^{\Omega(\log n)}$ under the exponential time hypothesis.{{r|tourdom}}
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)}$ ,{{r|vcdim}} and requires time $n^{(\log n)^{1/3-o(1)}}$ under the exponential time hypothesis.{{r|vc-hard}}

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.{{r|planted}}
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.{{r|mondual}}
Parity games, involving token-passing along the edges of a colored directed graph.{{r|parity}} The paper giving a quasi-polynomial algorithm for these games won the 2021 Nerode Prize.{{r|nerode}}

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.{{r|graphiso}}
The unknotting problem, recognizing whether a knot diagram describes the unknot, announced by Marc Lackenby in 2021.{{r|unknot}}

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,{{r|mwt}} finding the maximum clique on the intersection graph of disks,{{r|disk-clique}} and determining the probability that a hypergraph becomes disconnected when some of its edges fail with given independent probabilities.{{r|unreliability}}

More strongly, the problem of finding an approximate Nash equilibrium has a QPTAS, but cannot have a PTAS under the exponential time hypothesis.{{r|nash}}

References

{{reflist|refs=

{{citation

| last1 = Agrawal | first1 = Manindra | author1-link = Manindra Agrawal

| last2 = Kayal | first2 = Neeraj | author2-link = Neeraj Kayal

| last3 = Saxena | first3 = Nitin | author3-link = Nitin Saxena

| doi = 10.4007/annals.2004.160.781

| issue = 2

| journal = Annals of Mathematics

| jstor = 3597229

| pages = 781–793

| title = PRIMES is in P

| url = https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

| volume = 160

| year = 2004}}

{{citation

| last1 = Adleman | first1 = Leonard M. | author1-link = Leonard Adleman

| last2 = Pomerance | first2 = Carl | author2-link = Carl Pomerance

| last3 = Rumely | first3 = Robert S. | author3-link = Robert Rumely

| doi = 10.2307/2006975

| issue = 1

| journal = Annals of Mathematics

| jstor = 2006975

| pages = 173–206

| title = On distinguishing prime numbers from composite numbers

| volume = 117

| year = 1983}}

{{citation

| last1 = Bonnet | first1 = Édouard

| last2 = Giannopoulos | first2 = Panos

| last3 = Kim | first3 = Eun Jung | author3-link = Eun Jung Kim (parameterized complexity)

| last4 = Rzazewski | first4 = Pawel

| last5 = Sikora | first5 = Florian

| editor1-last = Speckmann | editor1-first = Bettina | editor1-link = Bettina Speckmann

| editor2-last = Tóth | editor2-first = Csaba D.

| contribution = QPTAS and subexponential algorithm for maximum clique on disk graphs

| doi = 10.4230/LIPICS.SOCG.2018.12

| pages = 12:1–12:15

| publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik

| series = LIPIcs

| title = 34th International Symposium on Computational Geometry, SoCG 2018, June 11–14, 2018, Budapest, Hungary

| title-link = Symposium on Computational Geometry

| volume = 99

| year = 2018| doi-access = free

}}

{{citation

| last = Klarreich | first = Erica | author-link = Erica Klarreich

| date = January 14, 2017

| journal = Quanta Magazine

| title = Graph isomorphism vanquished — again

| url = https://www.quantamagazine.org/20170114-graph-isomorphism-babai-fix/}}

{{citation

| last = Kisfaludi-Bak | first = Sándor

| editor-last = Chawla | editor-first = Shuchi | editor-link = Shuchi Chawla

| contribution = Hyperbolic intersection graphs and (quasi)-polynomial time

| doi = 10.1137/1.9781611975994.100

| pages = 1621–1638

| title = Proceedings of the 31st Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020

| title-link = Symposium on Discrete Algorithms

| year = 2020| arxiv = 1812.03960

| isbn = 978-1-61197-599-4

}}

{{citation

| last1 = Eppstein | first1 = David | author1-link = David Eppstein

| last2 = Lincoln | first2 = Andrea

| last3 = Williams | first3 = Virginia Vassilevska | author3-link = Virginia Vassilevska Williams

| doi = 10.7155/jgaa.00625

| issue = 5

| journal = Journal of Graph Algorithms and Applications

| pages = 329–339

| title = Quasipolynomiality of the smallest missing induced subgraph

| volume = 27

| year = 2023| doi-access = free

| arxiv = 2306.11185

}}

{{citation

| last1 = Eiter | first1 = Thomas

| last2 = Makino | first2 = Kazuhisa

| last3 = Gottlob | first3 = Georg

| doi = 10.1016/j.dam.2007.04.017

| issue = 11

| journal = Discrete Applied Mathematics

| mr = 2437000

| pages = 2035–2049

| title = Computational aspects of monotone dualization: a brief survey

| volume = 156

| year = 2008| doi-access = free

}}

{{citation

| last1 = Remy | first1 = Jan

| last2 = Steger | first2 = Angelika | author2-link = Angelika Steger

| at = Article A15

| doi = 10.1145/1516512.1516517

| issue = 3

| journal = Journal of the ACM

| title = A quasi-polynomial time approximation scheme for minimum weight triangulation

| volume = 56

| year = 2009}}

{{citation

| last1 = Braverman | first1 = Mark | author1-link = Mark Braverman (mathematician)

| last2 = Kun-Ko | first2 = Young

| last3 = Weinstein | first3 = Omri

| editor-last = Indyk | editor-first = Piotr | editor-link = Piotr Indyk

| contribution = Approximating the best Nash equilibrium in $n^{o(\log n)}$ -time breaks the Exponential Time Hypothesis

| doi = 10.1137/1.9781611973730.66

| pages = 970–982

| title = Proceedings of the 26th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4–6, 2015

| title-link = Symposium on Discrete Algorithms

| year = 2015}}

{{citation|url=https://eatcs.org/index.php/nerode-prize|title=IPEC Nerode Prize|work=EATCS |access-date=2023-12-03 |last1=Chita |first1=Efi }}

{{citation

| last1 = Calude | first1 = Cristian S.

| last2 = Jain | first2 = Sanjay

| last3 = Khoussainov | first3 = Bakhadyr

| last4 = Li | first4 = Wei

| last5 = Stephan | first5 = Frank

| doi = 10.1137/17M1145288

| issue = 2

| journal = SIAM Journal on Computing

| mr = 4413072

| pages = STOC17-152–STOC17-188

| title = Deciding parity games in quasi-polynomial time

| volume = 51

| year = 2022| hdl = 2292/31757

| hdl-access = free

}}

{{citation

| last1 = Hazan | first1 = Elad

| last2 = Krauthgamer | first2 = Robert

| doi = 10.1137/090766991

| issue = 1

| journal = SIAM Journal on Computing

| mr = 2765712

| pages = 79–91

| title = How hard is it to approximate the best Nash equilibrium?

| volume = 40

| year = 2011| citeseerx = 10.1.1.511.4422

}}

{{citation

| last1 = Megiddo | first1 = Nimrod | author1-link = Nimrod Megiddo

| last2 = Vishkin | first2 = Uzi | author2-link = Uzi Vishkin

| doi = 10.1016/0304-3975(88)90131-4

| issue = 2–3

| journal = Theoretical Computer Science

| mr = 980249

| pages = 307–316

| title = On finding a minimum dominating set in a tournament

| volume = 61

| year = 1988}}. This paper predates the formulation of the exponential time hypothesis, but proves that a solution to the minimum dominating set in a tournament could be used to solve Boolean satisfiability with $m$ clauses and $O(\log^2 m)$ variables, which requires time exponential in the number of variables according to the exponential time hypothesis.

{{citation|url=https://www.maths.ox.ac.uk/node/38304|title=Marc Lackenby announces a new unknot recognition algorithm that runs in quasi-polynomial time|date=2021-02-03|publisher=Mathematical Institute, University of Oxford|accessdate=2021-02-03}}

{{citation

| last1 = Cen | first1 = Ruoxu

| last2 = Li | first2 = Jason

| last3 = Panigrahi | first3 = Debmalya

| editor1-last = Mohar | editor1-first = Bojan

| editor2-last = Shinkar | editor2-first = Igor

| editor3-last = O'Donnell | editor3-first = Ryan

| arxiv = 2403.18781

| contribution = Hypergraph unreliability in quasi-polynomial time

| doi = 10.1145/3618260.3649753

| pages = 1700–1711

| publisher = {ACM}

| title = Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024

| year = 2024| isbn = 979-8-4007-0383-6

}}

{{citation

| last1 = Papadimitriou | first1 = Christos H. | author1-link = Christos Papadimitriou

| last2 = Yannakakis | first2 = Mihalis | author2-link = Mihalis Yannakakis

| doi = 10.1006/jcss.1996.0058

| issue = 2

| journal = Journal of Computer and System Sciences

| mr = 1418886

| pages = 161–170

| title = On limited nondeterminism and the complexity of the V-C dimension

| volume = 53

| year = 1996| doi-access = free

}}

{{citation

| last = Manurangsi | first = Pasin

| editor-last = Kalai | editor-first = Yael Tauman

| arxiv = 2211.01443

| contribution = Improved inapproximability of VC dimension and Littlestone's dimension via (unbalanced) biclique

| doi = 10.4230/LIPIcs.ITCS.2023.85

| pages = 85:1–85:18

| publisher = Schloss Dagstuhl - Leibniz-Zentrum für Informatik

| series = LIPIcs

| title = 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA

| volume = 251

| year = 2023| doi-access = free

}}

Category:Analysis of algorithms

Category:Complexity classes

Category:Computational complexity theory