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

Текущая версия на 06:50, 4 мая 2023

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

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