Quasi-polynomial time

Last updated

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 such that the worst-case running time of the algorithm, on inputs of size , has an upper bound of the form

Contents

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]

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:

Other problems for which the best known algorithm takes quasi-polynomial time include:

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

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

References

  1. Complexity Zoo : Class QP: Quasipolynomial-Time
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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 . 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 clauses and variables, which requires time exponential in the number of variables according to the exponential time hypothesis.
  7. 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
  8. Manurangsi, Pasin (2023), "Improved inapproximability of VC dimension and Littlestone's dimension via (unbalanced) biclique", in Kalai, Yael Tauman (ed.), 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, LIPIcs, vol. 251, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 85:1–85:18, arXiv: 2211.01443 , 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, CiteSeerX   10.1.1.511.4422 , doi:10.1137/090766991, MR   2765712
  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 , MR   2437000
  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, hdl: 2292/31757 , MR   4413072
  12. Chita, Efi, "IPEC Nerode Prize", EATCS, retrieved 2023-12-03
  13. Klarreich, Erica (January 14, 2017), "Graph isomorphism vanquished — again", Quanta Magazine
  14. 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
  15. 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
  16. 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 , ISBN   978-3-95977-066-8
  17. Cen, Ruoxu; Li, Jason; Panigrahi, Debmalya (2024), "Hypergraph unreliability in quasi-polynomial time", in Mohar, Bojan; Shinkar, Igor; O'Donnell, Ryan (eds.), Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, {ACM}, pp. 1700–1711, arXiv: 2403.18781 , doi:10.1145/3618260.3649753, ISBN   979-8-4007-0383-6
  18. Braverman, Mark; Kun-Ko, Young; Weinstein, Omri (2015), "Approximating the best Nash equilibrium in -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