Просмотр исходного текста страницы Теорема Сэвича. Совпадение классов NPS и PS

=Теорема Сэвича=

{{Теорема
|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> памяти.
|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>.

Пусть <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> переходов:

  '''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>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>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>\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>. Так что хотя бы одно из рассмотренных включений {{---}} строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения {{---}} строгие.

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

=Источники=
* Michael Sipser. Introduction to the theory of computation.

[[Категория: Теория сложности]]