Изменения

='''Класс ''' ''PS''Теорема Сэвича= == Определение =={{Определение |definition='''Класс''' <tex>PS(PSPACE)</tex> {{---}} класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера.<tex>PS=\bigcup\limits_{p(n)-poly} DSPACE(p(n))</tex>}}

Для любой <tex>f(n) \ge \log n </tex> справедливо: <tex>P \mathrm{NSPACE}(f(n)) \subseteq PS\mathrm{DSPACE}(f(n)^2)</tex>. <br> То есть, если недетерминированная машина Тьюринга может решить проблему, используя <tex>f(n)</tex> памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем <tex>f(n)^2</tex>памяти.|proof = Рассмотрим любой язык машину Тьюринга с входной и рабочей лентой. Ее конфигурацию <tex>I</tex> можно закодировать так: закодировать позицию и содержание рабочей ленты (займет <tex>LO(\log (f(n)))+O(f(n))</tex> из памяти), позицию входной ленты (займет <tex>PO(\log n)</tex>памяти). Так как <tex>f(n) \ge \log n </tex>, то размер конфигурации составит <tex>O(f(n))</tex>. Пусть <tex>L \in P\mathrm{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) // запись (I <tex>\vdash</tex> J) означает возможность перехода МТ из конфигурации 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>m</tex>, распознающая распознающую язык <tex>L</tex> за полиномиальное время. Это значит, что Эта машина может иметь <tex>2^{df(n)}</tex> конфигураций. Объясняется это следующим образом. Пусть <tex>m</tex> не успеет использовать памятьимеет <tex>c</tex> состояний и <tex>g</tex> символов ленточного алфавита. Количество различных строчек, размер которой превосходит полиномиальное значениекоторые могут появиться на рабочей ленте <tex>g^{f(n)}</tex>. Тогда любой язык Головка на входной ленте может быть в одной из <tex>n</tex> позиций и в одной из <tex>Pf(n)</tex> принадлежит на рабочей ленте. Таким образом, общее количество всех возможных конфигураций не превышает <tex>PScnf(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

{{Теорема|statement =Если слово принадлежит языку, то оно будет допущено, так как будут рассмотрены все возможные пути допуска. Это обеспечивается указанной нам глубиной рекурсии для функции <tex>NP \subseteq PSReach</tex>.|proof = Рассмотрим любой язык И если слово не допускается за <tex>L2^{df(n)}</tex> из шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено. В итоге функция <tex>NPReach</tex>. Так как имеет глубину рекурсии <tex>L \in NP</tex>, то существует программа-верификатор <tex>Rlog{2}^{df(n)}=O(f(x,yn))</tex>, что для каждого слова из на каждом уровне рекурсии используется <tex>L</tex> O(f(и только для нихn)) существует сертификат <tex>y</tex> полиномиальной длины, такой, что <tex>R</tex> допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины, а для этого необходим полиномиальный размер памяти. Тогда любой язык из всего эта функция использует <tex>NP</tex> принадлежит <tex>PSO(f(n)^2)</tex>памяти.

{{Теорема|statement ==Следствие==<tex>L \subseteq P</tex>.|proof mathrm{PS}= Машина Тьюринга, распознающая язык из <tex>L</tex>, используя не более <tex>O(\log n)</tex> памяти, работает не более чем <tex>| \Sigma |^mathrm{O(\log n)NPS} = poly(n)</tex> времени.}}

=== Вывод===<tex>\mathrm{L } \subseteq \mathrm{P } \subseteq \mathrm{NP } \subseteq \mathrm{PS} = \mathrm{NPS}</tex>.

Известно, что <tex>\mathrm{L } \neq \mathrm{PS } </tex>. Так что хотя бы одно из рассмотренных включений {{---}} строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения {{---}} строгие.

=Теорема СэвичаСм. также =*[[Класс PS. Связь класса PS с другими классами теории сложности]]

{{Теорема|statement =Источники=Для любой <tex>f(n) \ge \log n </tex> справедливо: <tex>NSPACE(f(n)) \subseteq DSPACE(f(n)^2)</tex>* Michael Sipser. Introduction to the theory of computation. <br>