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