Изменения
Перейти к:
навигация
,
поиск
← Предыдущая правка
Следующая правка →
Теорема о ёмкостной иерархии
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>
Теорема доказана.
Анонимный участник
192.168.0.2
Навигация
Персональные инструменты
Создать учётную запись
Войти
Пространства имён
Статья
Обсуждение
Варианты
Просмотры
Читать
Просмотр вики-текста
История
Ещё
Поиск
Навигация
Заглавная страница
Свежие правки
Случайная статья
Справка
Инструменты
Спецстраницы