Изменения
Нет описания правки
|definition='''Класс''' <tex>PS(PSPACE)</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера.
<tex>PS=\bigcup\limits_{p(n)-poly} DSPACE(p(n))</tex>
}}
{{Определение
|definition='''Класс''' <tex>NPS(NPSPACE)</tex> {{---}} класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера.
<tex>NPS=\bigcup\limits_{p(n)-poly} NSPACE(p(n))</tex>
}}
|statement =
<tex>L \subseteq P</tex>.
|proof = Машина Тьюринга, распознающая язык из <tex>L</tex>, используя не более <tex>O(\log n)</tex> памяти, работает не более чем <tex>| \Sigma |2^{O(\log n)} = poly(n)</tex> времени.
}}
То есть, если недетерминированная машина Тьюринга может решить проблему используя <tex>f(n)</tex> памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем <tex>f(n)^2</tex> памяти.
|proof =
Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию <tex>I</tex> можно закодировать так: закодировать позицию и содержание рабочей ленты (займет <tex>O(\log n)+O(f(n))</tex> памяти), содержание входной ленты (займет <tex>O(n)</tex> памяти).
Так как <tex>f(n) \ge \log n </tex>, то размер конфигурации составит <tex>O(f(n))</tex>.
Пусть <tex>L \in NSPACE(f(n))</tex>. Тогда существует недетерминированная машина Тьюринга, распознающая этот язык.<br>
Рассмотрим функцию <tex>Reach(I, J, k)</tex>, вычисляющую возможность перехода из конфигурации <tex>I</tex> в конфигурацию <tex>J</tex> за <tex>2^k</tex> переходов:
'''Reach''' (I, J, k)
'''if''' (k = 0)
'''return''' (I <tex>\vdash</tex> J) or (I = J);
'''else'''
'''for''' (Y) // перебор промежуточных конфигураций
'''if''' Reach(I, Y, k-1) and Reach(Y, J, k-1)
'''return''' true;
'''return''' false;
Эта функция имеет глубину рекурсии <tex>O(k)</tex>, на каждом уровне рекурсии использует <tex>O(f(n))</tex> памяти для хранения текущих конфигураций. Тогда всего функция использует <tex>O(kf(n))</tex> памяти.
Рассмотрим машину Тьюринга <tex>M</tex>, распознающую язык <tex>L</tex>. Эта машина может иметь <tex>2^{df(n)}</tex> конфигураций. Объясняется это следующим образом. Пусть <tex>M</tex> имеет <tex>c</tex> состояний и <tex>g</tex> символов ленточного алфавита. Количество различных строчек, которые могут появиться на рабочей ленте <tex>g^{f(n)}</tex>. Головка на входной ленте может быть в одной из n позиций и в одной из <tex>f(n)</tex> на рабочей ленте. Таким образом, общее количество всех возможных конфигураций не превышает <tex>cnf(n)g^{f(n)}=2^{\log c + \log n + \log (f(n)) + f(n) \log g}=2^{O(f(n))}</tex>.
Рассмотрим функцию, которая по заданному слову <tex>x</tex> проверяет его принадлежность к языку <tex>L</tex>:
'''Check''' (x, L)
'''for''' (T) // перебор конфигураций, которые содержат допускающие состояния
'''if''' Reach(S, T, <tex>\log \left(2^{df(n)}\right)</tex>)
'''return''' true;
'''return''' false;
В итоге функция <tex>Reach</tex> имеет глубину рекурсии <tex>\log{2}^{df(n)}=O(f(n))</tex>, на каждом уровне рекурсии используется <tex>O(f(n))</tex> памяти. Тогда всего эта функция использует <tex>O(f(n)^2)</tex> памяти.
}}
==Следствие==
<tex>PS=NPS</tex>
=Источники=
* Michael Sipser. Introduction to the theory of computation.
