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 [math]\displaystyle{ c }[/math] such that the worst-case running time of the algorithm, on inputs of size [math]\displaystyle{ n }[/math], has an upper bound of the form [math]\displaystyle{ 2^{O\bigl((\log n)^c\bigr)}. }[/math]
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]
- [math]\displaystyle{ \mathsf{QP} = \bigcup_{c \in \mathbb{N}} \mathsf{DTIME} \left(2^{(\log n)^c}\right) }[/math]
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:
- 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 unknotting problem, recognizing whether a knot diagram describes the unknot, announced by Marc Lackenby in 2021.[13]
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
- ↑ "On distinguishing prime numbers from composite numbers", Annals of Mathematics 117 (1): 173–206, 1983, doi:10.2307/2006975
- ↑ "PRIMES is in P", Annals of Mathematics 160 (2): 781–793, 2004, doi:10.4007/annals.2004.160.781, https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
- ↑ Kisfaludi-Bak, Sándor (2020), "Hyperbolic intersection graphs and (quasi)-polynomial time", 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, doi:10.1137/1.9781611975994.100
- ↑ "Quasipolynomiality of the smallest missing induced subgraph", Journal of Graph Algorithms and Applications 27 (5): 329–339, 2023, 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, doi:10.1137/090766991
- ↑ 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
- ↑ 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
- ↑ IPEC Nerode Prize, EATCS, https://eatcs.org/index.php/nerode-prize, retrieved 2023-12-03
- ↑ "On limited nondeterminism and the complexity of the V-C dimension", Journal of Computer and System Sciences 53 (2): 161–170, 1996, doi:10.1006/jcss.1996.0058
- ↑ "On finding a minimum dominating set in a tournament", Theoretical Computer Science 61 (2-3): 307–316, 1988, doi:10.1016/0304-3975(88)90131-4
- ↑ "Graph isomorphism vanquished — again", Quanta Magazine, January 14, 2017, https://www.quantamagazine.org/20170114-graph-isomorphism-babai-fix/
- ↑ Marc Lackenby announces a new unknot recognition algorithm that runs in quasi-polynomial time, Mathematical Institute, University of Oxford, 2021-02-03, https://www.maths.ox.ac.uk/node/38304, retrieved 2021-02-03
- ↑ Remy, Jan (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 (2018), "QPTAS and subexponential algorithm for maximum clique on disk graphs", 34th International Symposium on Computational Geometry, SoCG 2018, June 11–14, 2018, Budapest, Hungary, LIPIcs, 99, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 12:1–12:15, doi:10.4230/LIPICS.SOCG.2018.12
- ↑ "Approximating the best Nash equilibrium in [math]\displaystyle{ n^{o(\log n)} }[/math]-time breaks the Exponential Time Hypothesis", Proceedings of the 26th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4–6, 2015, 2015, pp. 970–982, doi:10.1137/1.9781611973730.66
 |  |
