Временная и пространственная сложность алгоритмов/Задачи/PSPACE in EXPTIME/Решение Мирошниченко Кирилла

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

Если язык определяется ДМТ М в f(n) пространства (где f(n) >= n). => SPACE(f(n)) ⊆ TIME(2^O(f(n))).

StasFomin (обсуждение) 13:41, 25 мая 2016 (UTC): Так где решение-то? Тут надо обосновать, для этого необходимо рассмотреть, как устроена машина Тьюринга. На семинарах разбирали.