Теорема о временной иерархии

Формулировка

Теорема о временной иерархии утверждает, что для любых двух конструируемых по времени функций [math]f\,\![/math] и [math]g\,\![/math] таких, что [math] \lim_{n \rightarrow \infty} t(f(n))/g(n) = 0[/math], выполняется [math]DTIME(g(n)) \ne DTIME(f(n))[/math].