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