Изменения

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

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

3 байта добавлено, 18:29, 18 марта 2010
→‎Доказательство
Получается, что <tex>L \in DSPACE(g(n)) \setminus DSPACE(f(n))</tex> и <tex>L \neq \emptyemptyset</tex>. Следовательно, <tex>DSPACE(g(n)) \neq DSPACE(f(n))</tex>
Теорема доказана.
Perovskaya
83
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/410»

Навигация