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 ...

, a function

f(n)

is said to exhibit quasi-polynomial growth when it 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

f(n)=2^

for some constant

c

, as expressed using

big O notation Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...

. That is, it is bounded by an exponential function of a polylogarithmic function. This generalizes the

polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...

s and the functions of polynomial growth, for which one can take

c=1

. A function with quasi-polynomial growth is also said to be quasi-polynomially bounded. Quasi-polynomial growth has been used in 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 ...

to describe certain algorithms whose

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...

is not polynomial, but is substantially smaller than exponential. In particular, algorithms whose worst-case running times exhibit quasi-polynomial growth are said to take quasi-polynomial time. As well as

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 ...

, some algorithms require quasi-polynomial

space complexity The space complexity of an algorithm or a data structure is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it exec ...

, use a quasi-polynomial number of parallel processors, can be expressed as algebraic formulas of quasi-polynomial size or have a quasi-polynomial competitive ratio. In some other cases, quasi-polynomial growth is used to model restrictions on the inputs to a problem that, when present, lead to good performance from algorithms on those inputs. It can also bound the size of the output for some problems; for instance, for the

shortest path problem In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between t ...

with linearly varying edge weights, the number of distinct solutions can be quasipolynomial. Beyond theoretical computer science, quasi-polynomial growth bounds have also been used in mathematics, for instance in partial results on the Hirsch conjecture for the diameter of polytopes in polyhedral combinatorics, or relating the sizes of cliques and independent sets in certain classes of graphs. However, in polyhedral combinatorics and

enumerative combinatorics Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an inf ...

, a different meaning of the same word also is used, for the quasi-polynomials, functions that generalize polynomials by having periodic coefficients.

References

{{reflist, refs= {{citation , last1 = Barth , first1 = Florian , last2 = Funke , first2 = Stefan , last3 = Proissl , first3 = Claudius , editor1-last = Chechik , editor1-first = Shiri , editor2-last = Navarro , editor2-first = Gonzalo , editor3-last = Rotenberg , editor3-first = Eva , editor4-last = Herman , editor4-first = Grzegorz , contribution = An upper bound on the number of extreme shortest paths in arbitrary dimensions , doi = 10.4230/LIPICS.ESA.2022.14 , pages = 14:1–14:12 , publisher = Schloss Dagstuhl - Leibniz-Zentrum für Informatik , series = LIPIcs , title = 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany , volume = 244 , year = 2022, doi-access = free {{citation , last = Carstensen , first = Patricia June , id = {{ProQuest, 303275648 , publisher = University of Michigan , series = Doctoral dissertation , title = The complexity of some problems in parametric linear and combinatorial programming , year = 1983 {{citation , last1 = Kalai , first1 = Gil , last2 = Kleitman , first2 = Daniel J. , doi = 10.1090/S0273-0979-1992-00285-9 , issue = 2 , journal = Bulletin of the American Mathematical Society , mr = 1130448 , pages = 315–316 , series = New Series , title = A quasi-polynomial bound for the diameter of graphs of polyhedra , volume = 26 , year = 1992, doi-access = free {{citation , last1 = McAllister , first1 = Tyrrell B. , last2 = Woods , first2 = Kevin M. , doi = 10.1016/j.jcta.2004.08.006 , issue = 2 , journal = Journal of Combinatorial Theory, Series A , mr = 2121031 , pages = 345–352 , title = The minimum period of the Ehrhart quasi-polynomial of a rational polytope , volume = 109 , year = 2005, doi-access = free , arxiv = math/0310255 {{citation , last1 = Bosek , first1 = Bartlomiej , last2 = Krawczyk , first2 = Tomasz , contribution = The sub-exponential upper bound for on-line chain partitioning , doi = 10.1109/FOCS.2010.40 , pages = 347–354 , publisher = IEEE Computer Society , title = 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA , year = 2010, isbn = 978-1-4244-8525-3 {{citation , last1 = Ackermann , first1 = Heiner , last2 = Newman , first2 = Alantha , last3 = Röglin , first3 = Heiko , last4 = Vöcking , first4 = Berthold , doi = 10.1016/j.tcs.2007.02.034 , issue = 3 , journal = Theoretical Computer Science , mr = 2325290 , pages = 253–270 , title = Decision-making based on approximate and smoothed Pareto curves , volume = 378 , year = 2007, doi-access = free {{citation , last1 = Fenner , first1 = Stephen , last2 = Gurjar , first2 = Rohit , last3 = Thierauf , first3 = Thomas , doi = 10.1137/16M1097870 , issue = 3 , journal = SIAM Journal on Computing , mr = 4277935 , pages = 218–235 , title = Bipartite perfect matching is in quasi-NC , volume = 50 , year = 2021, arxiv = 1601.06319 {{citation , last1 = Pilipczuk , first1 = Marek , last2 = Sokołowski , first2 = Michał , arxiv = 2202.07608 , doi = 10.1016/j.jctb.2023.02.006 , journal = Journal of Combinatorial Theory, Series B , mr = 4568111 , pages = 382–406 , title = Graphs of bounded twin-width are quasi-polynomially

\chi

-bounded , volume = 161 , year = 2023 {{citation , last1 = Fearnley , first1 = John , last2 = Jain , first2 = Sanjay , last3 = de Keijzer , first3 = Bart , last4 = Schewe , first4 = Sven , last5 = Stephan , first5 = Frank , last6 = Wojtczak , first6 = Dominik , doi = 10.1007/S10009-019-00509-3 , issue = 3 , journal = International Journal on Software Tools for Technology Transfer , pages = 325–349 , title = An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space , volume = 21 , year = 2019, arxiv = 1703.01296 {{citation , last = von zur Gathen , first = Joachim , doi = 10.1016/S0747-7171(87)80063-9 , issue = 2 , journal = Journal of Symbolic Computation , mr = 922386 , pages = 137–172 , title = Feasible arithmetic computations: Valiant's hypothesis , volume = 4 , year = 1987 Asymptotic analysis Computational complexity theory