Quasi-polynomial growth
In theoretical computer science, a function [math]\displaystyle{ f(n) }[/math] is said to exhibit quasi-polynomial growth when it has an upper bound of the form [math]\displaystyle{ f(n)=2^{O\bigl((\log n)^c\bigr)} }[/math] for some constant [math]\displaystyle{ c }[/math], 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 [math]\displaystyle{ c=1 }[/math]. 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]
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,[6] or relating the sizes of cliques and independent sets in certain classes of graphs.[7] 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.[8]
References
- ↑ 1.0 1.1 Ackermann, Heiner; Newman, Alantha; Röglin, Heiko; Vöcking, Berthold (2007), "Decision-making based on approximate and smoothed Pareto curves", Theoretical Computer Science 378 (3): 253–270, doi:10.1016/j.tcs.2007.02.034
- ↑ 2.0 2.1 von zur Gathen, Joachim (1987), "Feasible arithmetic computations: Valiant's hypothesis", Journal of Symbolic Computation 4 (2): 137–172, doi:10.1016/S0747-7171(87)80063-9
- ↑ Fearnley, John; Jain, Sanjay; de Keijzer, Bart; Schewe, Sven; Stephan, Frank; Wojtczak, Dominik (2019), "An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space", Int. J. Softw. Tools Technol. Transf. 21 (3): 325–349, doi:10.1007/S10009-019-00509-3
- ↑ Fenner, Stephen; Gurjar, Rohit; Thierauf, Thomas (2021), "Bipartite perfect matching is in quasi-NC", SIAM Journal on Computing 50 (3): 218–235, doi:10.1137/16M1097870
- ↑ Bosek, Bartlomiej; Krawczyk, Tomasz (2010), "The sub-exponential upper bound for on-line chain partitioning", 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, IEEE Computer Society, pp. 347–354, doi:10.1109/FOCS.2010.40
- ↑ Kalai, Gil; Kleitman, Daniel J. (1992), "A quasi-polynomial bound for the diameter of graphs of polyhedra", Bulletin of the American Mathematical Society, New Series 26 (2): 315–316, doi:10.1090/S0273-0979-1992-00285-9
- ↑ Pilipczuk, Marek; Sokołowski, Michał (2023), "Graphs of bounded twin-width are quasi-polynomially [math]\displaystyle{ \chi }[/math]-bounded", Journal of Combinatorial Theory, Series B 161: 382–406, doi:10.1016/j.jctb.2023.02.006
- ↑ McAllister, Tyrrell B.; Woods, Kevin M. (2005), "The minimum period of the Ehrhart quasi-polynomial of a rational polytope", Journal of Combinatorial Theory, Series A 109 (2): 345–352, doi:10.1016/j.jcta.2004.08.006
 |  |
