Wikipedia habla de dos grupos de funciones con asintótico de las tasas de crecimiento entre polinomial y exponencial – cuasi-polinomio funciones y sub-funciones exponenciales.
Sólo le da dos ejemplos de esta función, sin embargo, y esas funciones son de la forma $2^{(n^{1/3})}$ (el tiempo de ejecución del primer campo de tamiz) y $2^{(n \log n)^{1/2}}$ (el tiempo de ejecución de la gráfica isomorfismo problema). Ambas funciones tienen la propiedad de que $f(p(n))$ (donde $p$ es de algún polinomio) es todavía una función en $\Omega(2^n)$.
Hay un ejemplo de una función que no tiene esta propiedad? Específicamente, en términos de crecimiento de la conducta, quiero que el siguiente sea cierto para $f(n)$:
$f(n)$ crece más rápido que cualquier función polinomial, es decir, para cualquier polinomio $p(n)$, $f \notin O(p(n))$.
No polinomio de $f(n)$ crece más rápido que una función exponencial, es decir, para cualquier polinomio $p(n)$, una nueva función definida como $g(n) = f(p(n))$$o(2^n)$.
