Quasi-polynomial time

From HandWiki
Short description: Computational complexity class

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 size n, has an upper bound of the form 2O((log⁡n)c).

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]

QP=⋃c∈ℕDTIME(2(log⁡n)c)

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 the following problems:

  • Finding the largest disjoint subset of a collection of unit disks in the hyperbolic plane can be solved in time nO(log⁡n), and requires time nΩ(log⁡n) under the exponential time hypothesis.[4]
  • Finding a graph with the fewest vertices that does not appear as an induced subgraph of a given graph can be solved in time nO(log⁡n), and requires time nΩ(log⁡n) under the exponential time hypothesis.[5]
  • 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 nO(log⁡n), and requires time nΩ(log⁡n) under the exponential time hypothesis.[6]
  • 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 nO(log⁡n),[7] and requires time n(log⁡n)1/3−o(1) under the exponential time hypothesis.[8]

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.[9]
  • 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.[10]
  • Parity games, involving token-passing along the edges of a colored directed graph.[11] The paper giving a quasi-polynomial algorithm for these games won the 2021 Nerode Prize.[12]
  • 3-coloring circle graphs. These are the intersection graphs of chords of a circle. Finding their optimal colorings, in general, is NP-hard, as is testing whether they can be colored with four colors, but colorings with three colors can be found in time nO(log⁡n).[13]

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,[16] finding the maximum clique on the intersection graph of disks,[17] and determining the probability that a hypergraph becomes disconnected when some of its edges fail with given independent probabilities.[18]

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

References

  1. ↑ Complexity Zoo: Class QP: Quasipolynomial-Time
  2. ↑ "On distinguishing prime numbers from composite numbers", Annals of Mathematics 117 (1): 173–206, 1983, doi:10.2307/2006975 
  3. ↑ "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 
  4. ↑ 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, ISBN 978-1-61197-599-4 
  5. ↑ "Quasipolynomiality of the smallest missing induced subgraph", Journal of Graph Algorithms and Applications 27 (5): 329–339, 2023, doi:10.7155/jgaa.00625 
  6. ↑ "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 . 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(log2m) variables, which requires time exponential in the number of variables according to the exponential time hypothesis.
  7. ↑ "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 
  8. ↑ Manurangsi, Pasin (2023), "Improved inapproximability of VC dimension and Littlestone's dimension via (unbalanced) biclique", in Kalai, Yael Tauman, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, LIPIcs, 251, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 85:1–85:18, doi:10.4230/LIPIcs.ITCS.2023.85, ISBN 978-3-95977-263-1 
  9. ↑ 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 
  10. ↑ 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 
  11. ↑ 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 
  12. ↑ "IPEC Nerode Prize", EATCS, https://eatcs.org/index.php/nerode-prize, retrieved 2023-12-03 
  13. ↑ Ajaykrishnan, E. S.; Ganian, Robert; Lokshtanov, Daniel; Surianarayanan, Vaishali (2026), "A quasi-polynomial time algorithm for 3-coloring circle graphs", in Assadi, Sepehr; Rotenberg, Eva, 2026 Symposium on Simplicity in Algorithms, SOSA 2026, Vancouver, BC, Canada, January 12-14, 2026, SIAM, pp. 65–80, doi:10.1137/1.9781611978964.6 
  14. ↑ "Graph isomorphism vanquished — again", Quanta Magazine, January 14, 2017, https://www.quantamagazine.org/20170114-graph-isomorphism-babai-fix/ 
  15. ↑ 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 
  16. ↑ 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 
  17. ↑ 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, ISBN 978-3-95977-066-8 
  18. ↑ Cen, Ruoxu; Li, Jason; Panigrahi, Debmalya (2024), "Hypergraph unreliability in quasi-polynomial time", in Mohar, Bojan; Shinkar, Igor; O'Donnell, Ryan, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, {ACM}, pp. 1700–1711, doi:10.1145/3618260.3649753, ISBN 979-8-4007-0383-6 
  19. ↑ "Approximating the best Nash equilibrium in no(log⁡n)-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