Обсуждение:Теорема о ёмкостной иерархии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «"Любая такая машина использует памяти не более <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>."
  
Отсюда следует, что построенная машина принадлежит классу DTIME(f), что неверно. Кажется, должно быть что-то типа + константа в вышеприведенном утверждении.
+
Отсюда следует, что построенная машина принадлежит классу DSPACE(f), что неверно. Кажется, должно быть что-то типа + константа в вышеприведенном утверждении.

Текущая версия на 23:51, 31 января 2019

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

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