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

Версия 12:41, 24 декабря 2014

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

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