Временная и пространственная сложность алгоритмов/Задачи/PSPACE in EXPTIME — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 15 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
Докажите, что <m>PSPACE \subseteq EXPTIME </m>.
 
Докажите, что <m>PSPACE \subseteq EXPTIME </m>.
  
[[Category:На проверку]]
+
 
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->
  
Решение: Пусть L - язык, разрешаемый МТ с пространственной сложностью не больше n^k (рассматриваем одноленточную МТ, для большего числа лент аналогично). Пусть A - алфавит, Г - множество состояний. Тогда всего |A|^(n^k) возможных записей на ленте, |Г| возможных состояний, n^k возможных положений головки. Т.о. МТ всего может сделать не более (n^k) * |Г| * |A|^(n^k) шагов, т.к. иначе произойдет зацикливание: головка окажется в том же положении, в том же состоянии, с той же записью на ленте. Значит, время работы будет экспоненциально по длине входа.
+
[[Категория:Решенные задачи]]

Текущая версия на 10:41, 20 февраля 2020

Докажите, что .