Обсуждение:Теорема о ёмкостной иерархии

Материал из Викиконспекты
Версия от 23:51, 31 января 2019; Дмитрий Мурзин (обсуждение | вклад) (Дмитрий Мурзин переименовал страницу Обсуждение:Теорема о емкостной иерархии в Обсуждение:Теорема о ёмкостной иерархии: Ёфикация)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

"Любая такая машина использует памяти не более [math]f(|\langle m_1,x\rangle|)[/math]."

Отсюда следует, что построенная машина принадлежит классу DSPACE(f), что неверно. Кажется, должно быть что-то типа + константа в вышеприведенном утверждении.

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение:Теорема_о_ёмкостной_иерархии&oldid=69808»