Изменения

Перейти к: навигация, поиск

Теорема о ёмкостной иерархии

8 байт добавлено, 17:14, 18 марта 2010
Доказательство
Получается, что <math>L \in DSPACE(g(n)) \ setminus DSPACE(f(n))</math> и <math>L \neq \empty</math>. Следовательно, <math>DSPACE(g(n)) \neq DSPACE(f(n))</math>
Теорема доказана.
Анонимный участник

Навигация