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 has an upper bound of the form
$2^.$

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.
:$\mathsf = \bigcup_ \mathsf \left(2^\right)$

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 $n^$, and requires time $n^$ 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 $n^$, and requires time $n^$ 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 $n^$, and requires time $n^$ under the exponential time hypothesis.
*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^$, and requires time $n^$ 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:
*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.
*The unknotting problem, recognizing whether a knot diagram describes the unknot, announced by Marc Lackenby in 2021.

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

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

{{ComplexityZoo, Class QP: Quasipolynomial-Time, Q#qp

Analysis of algorithms
Complexity classes
Computational complexity theory