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