Теорема Сэвича. Совпадение классов NPS и PS

Материал из Викиконспекты
Перейти к: навигация, поиск

Класс PS

Определение

Определение:
[math]\mathrm{PS}[/math] [math]\mathrm{(PSPACE)}[/math] — класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера.
[math]\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))[/math].


Определение:
[math]\mathrm{NPS}[/math] [math]\mathrm{(NPSPACE)}[/math] — класс языков, разрешимых на недетерминированной машине Тьюринга с использованием памяти полиномиального размера.
[math]\mathrm{NPS}=\bigcup\limits_{p(n) \in poly} \mathrm{NSPACE}(p(n))[/math].


Связь класса PS с другими классами теории сложности

Теорема:
[math]\mathrm{P} \subseteq \mathrm{PS}[/math].
Доказательство:
[math]\triangleright[/math]
Рассмотрим любой язык [math]L[/math] из [math]\mathrm{P}[/math]. Так как [math]L \in \mathrm{P}[/math], то существует машина Тьюринга [math]m[/math], распознающая [math]L[/math] за полиномиальное время. Это значит, что [math]m[/math] не сможет использовать более, чем полиномиальное количество памяти, следовательно [math] L \in \mathrm{PS}[/math].
[math]\triangleleft[/math]
Теорема:
[math]\mathrm{NP} \subseteq \mathrm{PS}[/math].
Доказательство:
[math]\triangleright[/math]
Рассмотрим любой язык [math]L[/math] из [math]\mathrm{NP}[/math]. Так как [math]L \in \mathrm{NP}[/math], то существует программа-верификатор [math]R(x,y)[/math], что для каждого слова из [math]L[/math] (и только для них) существует такой сертификат [math]y[/math] полиномиальной длины, что [math]R[/math] допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины. Для этого необходим полиномиальный размер памяти. Из этого следует, что [math]L \in \mathrm{PS}[/math].
[math]\triangleleft[/math]

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

Теорема:
Для любой [math]f(n) \ge \log n [/math] справедливо: [math]\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)[/math].
То есть, если недетерминированная машина Тьюринга может решить проблему, используя [math]f(n)[/math] памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем [math]f(n)^2[/math] памяти.
Доказательство:
[math]\triangleright[/math]

Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию [math]I[/math] можно закодировать так: закодировать позицию и содержание рабочей ленты (займет [math]O(\log (f(n)))+O(f(n))[/math] памяти), позицию входной ленты (займет [math]O(\log n)[/math] памяти). Так как [math]f(n) \ge \log n [/math], то размер конфигурации составит [math]O(f(n))[/math].

Пусть [math]L \in \mathrm{NSPACE}(f(n))[/math]. Тогда существует недетерминированная машина Тьюринга, распознающая этот язык.
Рассмотрим вспомогательную функцию [math]Reach(I, J, k)[/math], вычисляющую возможность перехода из конфигурации [math]I[/math] в конфигурацию [math]J[/math] за не более, чем [math]2^k[/math] переходов: 

 Reach(I, J, k):
   if (k = 0)
     return (I [math]\vdash[/math] J) or (I = J)
   // запись (I [math]\vdash[/math] J) означает возможность перехода МТ из конфигурации I в конфигурацию J за один шаг
   else
     for (Y) // перебор промежуточных конфигураций
       if Reach(I, Y, k-1) and Reach(Y, J, k-1)
         return true
   return false

Эта функция имеет глубину рекурсии [math]O(k)[/math], на каждом уровне рекурсии использует [math]O(f(n))[/math] памяти для хранения текущих конфигураций.

Рассмотрим машину Тьюринга [math]m[/math], распознающую язык [math]L[/math]. Эта машина может иметь [math]2^{df(n)}[/math] конфигураций. Объясняется это следующим образом. Пусть [math]m[/math] имеет [math]c[/math] состояний и [math]g[/math] символов ленточного алфавита. Количество различных строчек, которые могут появиться на рабочей ленте [math]g^{f(n)}[/math]. Головка на входной ленте может быть в одной из [math]n[/math] позиций и в одной из [math]f(n)[/math] на рабочей ленте. Таким образом, общее количество всех возможных конфигураций не превышает [math]cnf(n)g^{f(n)}=2^{\log c + \log n + \log (f(n)) + f(n) \log g}=2^{O(f(n))}[/math].

Рассмотрим функцию, которая по заданному слову [math]x[/math] проверяет его принадлежность к языку [math]L[/math]: 

 Check(x, L):
   for (T) // перебор конфигураций, которые содержат допускающие состояния
     if Reach(S, T, [math]\log \left(2^{df(n)}\right)[/math])
       return true
   return false

Если слово принадлежит языку, то оно будет допущено, так как будут рассмотрены все возможные пути допуска. Это обеспечивается указанной нам глубиной рекурсии для функции [math]Reach[/math]. И если слово не допускается за [math]2^{df(n)}[/math] шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено.

В итоге функция [math]Reach[/math] имеет глубину рекурсии [math]\log{2}^{df(n)}=O(f(n))[/math], на каждом уровне рекурсии используется [math]O(f(n))[/math] памяти. Тогда всего эта функция использует [math]O(f(n)^2)[/math] памяти.
[math]\triangleleft[/math]

Следствие

[math]\mathrm{PS}=\mathrm{NPS}[/math]

Вывод

[math]\mathrm{L} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PS} = \mathrm{NPS}[/math].

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


Источники

  • Michael Sipser. Introduction to the theory of computation.
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Сэвича._Совпадение_классов_NPS_и_PS&oldid=23351»