Теорема о ёмкостной иерархии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Формулировка)
(Формулировка)
Строка 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

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

Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций [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].