Временная и пространственная сложность алгоритмов/Задачи/l-eq-p-then-pspace-eq-exptime

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

Покажите, что если DLOGSPACE = P, то PSPACE = EXPTIME.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.

Источник — «https://discopal.ispras.ru/index.php?title=Временная_и_пространственная_сложность_алгоритмов/Задачи/l-eq-p-then-pspace-eq-exptime&oldid=25752»