Обсуждение:Теорема о ёмкостной иерархии — различия между версиями
(Новая страница: «"Любая такая машина использует памяти не более <tex>f(|\langle m_1,x\rangle|)</tex>." Отсюда следует, что п…») |
м (Дмитрий Мурзин переименовал страницу Обсуждение:Теорема о емкостной иерархии в Обсуждение:Теорема о ёмкостной иерархии: Ёфикация) |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 1: | Строка 1: | ||
"Любая такая машина использует памяти не более <tex>f(|\langle m_1,x\rangle|)</tex>." | "Любая такая машина использует памяти не более <tex>f(|\langle m_1,x\rangle|)</tex>." | ||
| − | Отсюда следует, что построенная машина принадлежит классу | + | Отсюда следует, что построенная машина принадлежит классу DSPACE(f), что неверно. Кажется, должно быть что-то типа + константа в вышеприведенном утверждении. |
Текущая версия на 23:51, 31 января 2019
"Любая такая машина использует памяти не более ."
Отсюда следует, что построенная машина принадлежит классу DSPACE(f), что неверно. Кажется, должно быть что-то типа + константа в вышеприведенном утверждении.
