Участник:Romanvin/Решение задач/Временная и пространственная сложность алгоритмов/Задачи/ex-limited-halt

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


ДМТ M, как и любая ДМТ, может за один шаг написать максимум один новый символ на ленте вместо пустого символа. Значит, за t шагов будет использовано максимум t новых ячейки, в сумме (|x| + t) ячейки. Значит, задача принадлежит PSPACE, а значит, и EXPTIME.


StasFomin 23:42, 15 мая 2019 (MSK): У вас неверное понимание класса PSPACE. PSPACE — «есть не больше ячеек, чем полином от длины входа». Если он у вас ест t ячеек, а на входе число t — подумайте, в каких они отношениях находятся.