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
{\displaystyle c}
such that the
worst-case running time of the algorithm, on inputs of size
n
{\displaystyle n}
, has an
upper bound of the form
2
O
(
(
log
n
)
c
)
.
{\displaystyle 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.
[1]
Q
P
=
⋃
c
∈
N
D
T
I
M
E
(
2
(
log
n
)
c
)
{\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
exponential time hypothesis or a related
computational hardness assumption . For instance, this is true for finding the largest disjoint subset of a collection of
unit disks in the
hyperbolic plane ,
[4] and for finding a graph with the fewest vertices that does not appear as an
induced subgraph of a given graph.
[5]
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.
[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:
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 ,
[14] and finding the
maximum clique on the
intersection graph of disks.
[15]
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
^
Complexity Zoo :
Class QP: Quasipolynomial-Time
^
Adleman, Leonard M. ;
Pomerance, Carl ;
Rumely, Robert S. (1983), "On distinguishing prime numbers from composite numbers",
Annals of Mathematics , 117 (1): 173–206,
doi :
10.2307/2006975 ,
JSTOR
2006975
^
Agrawal, Manindra ;
Kayal, Neeraj ;
Saxena, Nitin (2004),
"PRIMES is in P" (PDF) ,
Annals of Mathematics , 160 (2): 781–793,
doi :
10.4007/annals.2004.160.781 ,
JSTOR
3597229
^ Kisfaludi-Bak, Sándor (2020), "Hyperbolic intersection graphs and (quasi)-polynomial time", in
Chawla, Shuchi (ed.),
Proceedings of the 31st Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020 , pp. 1621–1638,
arXiv :
1812.03960 ,
doi :
10.1137/1.9781611975994.100 ,
ISBN
978-1-61197-599-4
^
Eppstein, David ; Lincoln, Andrea;
Williams, Virginia Vassilevska (2023), "Quasipolynomiality of the smallest missing induced subgraph",
Journal of Graph Algorithms and Applications , 27 (5): 329–339,
arXiv :
2306.11185 ,
doi :
10.7155/jgaa.00625
^ Hazan, Elad; Krauthgamer, Robert (2011), "How hard is it to approximate the best Nash equilibrium?",
SIAM Journal on Computing , 40 (1): 79–91,
CiteSeerX
10.1.1.511.4422 ,
doi :
10.1137/090766991 ,
MR
2765712
^ Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008), "Computational aspects of monotone dualization: a brief survey",
Discrete Applied Mathematics , 156 (11): 2035–2049,
doi :
10.1016/j.dam.2007.04.017 ,
MR
2437000
^ Calude, Cristian S.; Jain, Sanjay; Khoussainov, Bakhadyr; Li, Wei; Stephan, Frank (2022), "Deciding parity games in quasi-polynomial time",
SIAM Journal on Computing , 51 (2): STOC17-152–STOC17-188,
doi :
10.1137/17M1145288 ,
hdl :
2292/31757 ,
MR
4413072
^
IPEC Nerode Prize , EATCS, retrieved 2023-12-03
^
Papadimitriou, Christos H. ;
Yannakakis, Mihalis (1996), "On limited nondeterminism and the complexity of the V-C dimension",
Journal of Computer and System Sciences , 53 (2): 161–170,
doi :
10.1006/jcss.1996.0058 ,
MR
1418886
^
Megiddo, Nimrod ;
Vishkin, Uzi (1988), "On finding a minimum dominating set in a tournament",
Theoretical Computer Science , 61 (2–3): 307–316,
doi :
10.1016/0304-3975(88)90131-4 ,
MR
0980249
^
Klarreich, Erica (January 14, 2017),
"Graph isomorphism vanquished — again" ,
Quanta Magazine
^
Marc Lackenby announces a new unknot recognition algorithm that runs in quasi-polynomial time , Mathematical Institute,
University of Oxford , 2021-02-03, retrieved 2021-02-03
^ Remy, Jan;
Steger, Angelika (2009), "A quasi-polynomial time approximation scheme for minimum weight triangulation",
Journal of the ACM , 56 (3), Article A15,
doi :
10.1145/1516512.1516517
^ Bonnet, Édouard; Giannopoulos, Panos;
Kim, Eun Jung ; Rzazewski, Pawel; Sikora, Florian (2018), "QPTAS and subexponential algorithm for maximum clique on disk graphs", in
Speckmann, Bettina ; Tóth, Csaba D. (eds.),
34th International Symposium on Computational Geometry, SoCG 2018, June 11–14, 2018, Budapest, Hungary , LIPIcs, vol. 99, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 12:1–12:15,
doi :
10.4230/LIPICS.SOCG.2018.12
^
Braverman, Mark ; Kun-Ko, Young; Weinstein, Omri (2015), "Approximating the best Nash equilibrium in
n
o
(
log
n
)
{\textstyle n^{o(\log n)}}
-time breaks the Exponential Time Hypothesis", in
Indyk, Piotr (ed.),
Proceedings of the 26th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4–6, 2015 , pp. 970–982,
doi :
10.1137/1.9781611973730.66