Изменения
Нет описания правки
{{Определение
|definition='''Класс''' <tex>PS(PSPACE)</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера.
<tex>PS=\bigcup\limits_{p(n)-\in poly} DSPACE(p(n))</tex>
}}
{{Определение
|definition='''Класс''' <tex>NPS(NPSPACE)</tex> {{---}} класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера.
<tex>NPS=\bigcup\limits_{p(n)-\in poly} NSPACE(p(n))</tex>
}}
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>NP</tex>. Так как <tex>L \in NP</tex>, то существует программа-верификатор <tex>R(x,y)</tex>, что для каждого слова из <tex>L</tex> (и только для них) существует сертификат <tex>y</tex> полиномиальной длины, такой, что <tex>R</tex> допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины, а для этого необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>.
}}
=Теорема Сэвича=
То есть, если недетерминированная машина Тьюринга может решить проблему используя <tex>f(n)</tex> памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем <tex>f(n)^2</tex> памяти.
|proof =
Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию <tex>I</tex> можно закодировать так: закодировать позицию и содержание рабочей ленты (займет <tex>O(\log (f(n)))+O(f(n))</tex> памяти), содержание позицию входной ленты (займет <tex>O(\log n)</tex> памяти).
Так как <tex>f(n) \ge \log n </tex>, то размер конфигурации составит <tex>O(f(n))</tex>.
'''return''' false;
Если слово принадлежит языку, то оно будет допущено, так как будут рассмотрены все возможные пути допуска. Это обеспечивается указанной нам глубиной рекурсии для функции <tex>Reach</tex>. И если слово не допускается за <tex>2^{df(n)}</tex> шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено.
В итоге функция <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>
=Вывод=
<tex>L \subseteq P \subseteq NP \subseteq PS = NPS</tex>.
Известно, что <tex>L \neq PS </tex>. Так что хотя бы одно из рассмотренных включений {{---}} строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения {{---}} строгие.
=Источники=
* Michael Sipser. Introduction to the theory of computation.
