Quasi-polynomial growth

In theoretical computer science, a function $f(n)$ is said to exhibit quasi-polynomial growth when it has an upper bound of the form $f(n)=2^{O{\bigl (}(\log n)^{c}{\bigr )}}$ for some constant $c$ , as expressed using big O notation. That is, it is bounded by an exponential function of a polylogarithmic function. This generalizes the polynomials 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.^[1]

Quasi-polynomial growth has been used in the analysis of algorithms to describe certain algorithms whose computational complexity 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.^[2] As well as time complexity, some algorithms require quasi-polynomial space complexity,^[3] use a quasi-polynomial number of parallel processors,^[4] can be expressed as algebraic formulas of quasi-polynomial size^[2] or have a quasi-polynomial competitive ratio.^[5] 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.^[1] It can also bound the size of the output for some problems; for instance, for the shortest path problem with linearly varying edge weights, the number of distinct solutions can be quasipolynomial.^[6]^[7]

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,^[8] or relating the sizes of cliques and independent sets in certain classes of graphs.^[9] However, in polyhedral combinatorics and enumerative combinatorics, a different meaning of the same word also is used, for the quasi-polynomials, functions that generalize polynomials by having periodic coefficients.^[10]

^ ^a ^b Cite error: The named reference pareto was invoked but never defined (see the help page).
^ ^a ^b Cite error: The named reference vzg was invoked but never defined (see the help page).
^ Cite error: The named reference space was invoked but never defined (see the help page).
^ Cite error: The named reference qnc was invoked but never defined (see the help page).
^ Cite error: The named reference online was invoked but never defined (see the help page).
^ Cite error: The named reference carstensen was invoked but never defined (see the help page).
^ Cite error: The named reference bfp was invoked but never defined (see the help page).
^ Cite error: The named reference diam was invoked but never defined (see the help page).
^ Cite error: The named reference quasiX was invoked but never defined (see the help page).
^ Cite error: The named reference ehrhart was invoked but never defined (see the help page).

[pareto-1] Cite error: The named reference pareto was invoked but never defined (see the help page).

[vzg-2] Cite error: The named reference vzg was invoked but never defined (see the help page).

[space-3] Cite error: The named reference space was invoked but never defined (see the help page).

[qnc-4] Cite error: The named reference qnc was invoked but never defined (see the help page).

[online-5] Cite error: The named reference online was invoked but never defined (see the help page).

[carstensen-6] Cite error: The named reference carstensen was invoked but never defined (see the help page).

[bfp-7] Cite error: The named reference bfp was invoked but never defined (see the help page).

[diam-8] Cite error: The named reference diam was invoked but never defined (see the help page).

[quasiX-9] Cite error: The named reference quasiX was invoked but never defined (see the help page).

[ehrhart-10] Cite error: The named reference ehrhart was invoked but never defined (see the help page).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]