Теорема о ёмкостной иерархии — различия между версиями
Mashuna (обсуждение | вклад) (→Формулировка) |
Mashuna (обсуждение | вклад) (→Формулировка) |
||
| Строка 1: | Строка 1: | ||
== Формулировка == | == Формулировка == | ||
| − | '''Теорема о емкостной иерархии''' утверждает, что для любых двух конструируемых по памяти функций <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>. | + | '''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <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>. |
Версия 13:15, 10 марта 2010
Формулировка
Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций и таких, что , выполняется .
