Теорема Сэвича. Совпадение классов 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.