En matemáticas , una función polilogarítmica en n es un polinomio en el logaritmo de n ,
La notación log k n se utiliza a menudo como abreviatura de (log n ) k , análoga a sin 2 θ para (sin θ ) 2 .
En informática , las funciones polilogarítmicas ocurren como el orden del tiempo o la memoria utilizado por algunos algoritmos (p. ej., "tiene orden polilogarítmico"), como en la definición de QPTAS (ver PTAS ).
Todas las funciones polilogarítmicas de n son o( n ε ) para cada exponente ε > 0 (para conocer el significado de este símbolo, consulte la notación o pequeña ), es decir, una función polilogarítmica crece más lentamente que cualquier exponente positivo. Esta observación es la base de la notación O suave Õ( n ) .
Si una función está acotada por una función exponencial de una función polilogarítmica, se dice que exhibe un crecimiento cuasipolinomial . Esto se utiliza en la teoría de la complejidad computacional para definir el tiempo cuasipolinomial y los límites cuasipolinomiales en otras medidas de complejidad.
