computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

and the

analysis of algorithms In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that r ...

, an algorithm is said to take quasi-polynomial time if its

time complexity In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...

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 In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of . Dually, a lower bound or minorant of is defined to be an element of that is less ...

of the form

2^.

The

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...

s with quasi-polynomial time algorithms are natural candidates for being

NP-intermediate In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. Lad ...

, neither having

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

nor likely to be

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

Complexity class

The complexity class QP consists of all problems that have quasi-polynomial time algorithms. It can be defined in terms of

DTIME In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would ta ...

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 A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...

has subsequently been shown to have a polynomial time algorithm, the

AKS primality test The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientist ...

. In some cases, quasi-polynomial time bounds can be proven to be optimal under the exponential time hypothesis or a related

computational hardness assumption In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently (where ''efficiently'' typically means "in polynomial time"). It is not known how to prove (unconditi ...

. For instance, this is true for the following problems: *Finding the largest disjoint subset of a collection of

unit disk In mathematics, the open unit disk (or disc) around ''P'' (where ''P'' is a given point in the plane), is the set of points whose distance from ''P'' is less than 1: :D_1(P) = \.\, The closed unit disk around ''P'' is the set of points whose d ...

s in the

hyperbolic plane In mathematics, hyperbolic geometry (also called Lobachevskian geometry or Bolyai– Lobachevskian geometry) is a non-Euclidean geometry. The parallel postulate of Euclidean geometry is replaced with: :For any given line ''R'' and point ''P' ...

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 In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...

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 graph theory, a dominating set for a Graph (discrete mathematics), graph is a subset of its vertices, such that any vertex of is in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for ...

in a

tournament A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses: # One or more competitions held at a single venue and concen ...

. 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 In Vapnik–Chervonenkis theory, the Vapnik–Chervonenkis (VC) dimension is a measure of the size (capacity, complexity, expressive power, richness, or flexibility) of a class of sets. The notion can be extended to classes of binary functions. It ...

of a

family of sets In set theory and related branches of mathematics, a family (or collection) can mean, depending upon the context, any of the following: set, indexed set, multiset, or class. A collection F of subsets of a given set S is called a family of su ...

. 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 In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs l ...

has been modified by adding edges between all pairs of a subset of its vertices. *

Monotone dualization In theoretical computer science, monotone dualization is a computational problem of constructing the dual of a monotone Boolean function. Equivalent problems can also be formulated as constructing the transversal hypergraph of a given hypergraph, o ...

, 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 game A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a (single, shared) token along the edges of the graph. The ow ...

s, 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 The EATCS–IPEC Nerode Prize is a theoretical computer science prize awarded for outstanding research in the area of parameterized complexity, multivariate algorithmics. It is awarded by the European Association for Theoretical Computer Science an ...

. Problems for which a quasi-polynomial time algorithm has been announced but not fully published include: *The

graph isomorphism problem The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational c ...

, 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 László "Laci" Babai (born July 20, 1950, in Budapest) a fellow of the American Academy of Arts and Sciences, and won the Knuth Prize. Babai was an invited speaker at the International Congresses of Mathematicians in Kyoto (1990), Zürich (199 ...

. *The

unknotting problem In mathematics, the unknotting problem is the problem of algorithmically recognizing the unknot, given some representation of a knot, e.g., a knot diagram. There are several types of unknotting algorithms. A major unresolved challenge is to de ...

, recognizing whether a

knot diagram In topology, knot theory is the study of mathematical knots. While inspired by knots which appear in daily life, such as those in shoelaces and rope, a mathematical knot differs in that the ends are joined so it cannot be undone, the simplest k ...

describes the

unknot In the knot theory, mathematical theory of knots, the unknot, not knot, or trivial knot, is the least knotted of all knots. Intuitively, the unknot is a closed loop of rope without a Knot (mathematics), knot tied into it, unknotted. To a knot ...

, announced by

Marc Lackenby Marc Lackenby is a professor of mathematics at the University of Oxford whose research concerns knot theory, low-dimensional topology, and group theory. Lackenby studied mathematics at the University of Cambridge beginning in 1990, and earned his ...

in 2021.

In approximation algorithms

Quasi-polynomial time has also been used to study

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...

s. In particular, a ''quasi-polynomial-time approximation scheme'' (QPTAS) is a variant of a

polynomial-time approximation scheme In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an inst ...

whose running time is quasi-polynomial rather than polynomial. Problems with a QPTAS include minimum-weight triangulation, finding the

maximum clique In graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of th ...

on the

intersection graph In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...

of disks, and determining the probability that a

hypergraph In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...

becomes disconnected when some of its edges fail with given independent probabilities. More strongly, the problem of finding an approximate

Nash equilibrium In game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed) ...

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 The ''Annals of Mathematics'' is a mathematical journal published every two months by Princeton University and the Institute for Advanced Study. History The journal was established as ''The Analyst'' in 1874 and with Joel E. Hendricks as t ...

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

, 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 ''Quanta Magazine'' is an editorially independent online publication of the Simons Foundation covering developments in physics, mathematics, biology and computer science. History ''Quanta Magazine'' was initially launched as ''Simons Science ...

, 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 The ''Journal of Graph Algorithms and Applications'' is a diamond open access peer-reviewed scientific journal covering the subject of graph algorithms and graph drawing. The journal was established in 1997 and the current co-editors-in-chief are ...

, 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 ''Discrete Applied Mathematics'' is a peer-reviewed scientific journal covering algorithmic and applied areas of discrete mathematics. It is published by Elsevier and the editor-in-chief is Endre Boros (Rutgers University). The journal was split ...

, 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 The ''Journal of the ACM'' (''JACM'') is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is ...

, 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 The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation i ...

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

, 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 Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

, 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 The University of Oxford is a collegiate university, collegiate research university in Oxford, England. There is evidence of teaching as early as 1096, making it the oldest university in the English-speaking world and the List of oldest un ...

, 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 The ''Journal of Computer and System Sciences'' (JCSS) is a peer-reviewed scientific journal in the field of computer science. ''JCSS'' is published by Elsevier, and it was started in 1967. Many influential scientific articles have been published ...

, 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