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

Ссылки сюда (12) →

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

Решение: Пусть L - язык, разрешаемый МТ с пространственной сложностью не больше n^k (рассматриваем одноленточную МТ, для большего числа лент аналогично). Пусть A - алфавит, Г - множество состояний. Тогда всего |A|^(n^k) возможных записей на ленте, |Г| возможных состояний, n^k возможных положений головки. Т.о. МТ всего может сделать не более (n^k) * |Г| * |A|^(n^k) шагов, т.к. иначе произойдет зацикливание: головка окажется в том же положении, в том же состоянии, с той же записью на ленте. Значит, время работы будет экспоненциально по длине входа.

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

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

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