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

Класс PS

Определение

Определение:

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

Определение:

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

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

Теорема:

[math]P \subseteq PS[/math].

Доказательство:

[math]\triangleright[/math]

Рассмотрим любой язык [math]L[/math] из [math]P[/math]. Так как [math]L \in P[/math], то существует машина Тьюринга [math]m[/math], распознающая [math]L[/math] за полиномиальное время. Это значит, что [math]m[/math] не успеет использовать память, размер которой превосходит полиномиальное значение. Тогда любой язык из [math]P[/math] принадлежит [math]PS[/math].

[math]\triangleleft[/math]

Теорема:

[math]NP \subseteq PS[/math].

Доказательство:

[math]\triangleright[/math]

Рассмотрим любой язык [math]L[/math] из [math]NP[/math]. Так как [math]L \in NP[/math], то существует программа-верификатор [math]R(x,y)[/math], что для каждого слова из [math]L[/math] (и только для них) существует сертификат [math]y[/math] полиномиальной длины, такой, что [math]R[/math] допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины, а для этого необходим полиномиальный размер памяти. Тогда любой язык из [math]NP[/math] принадлежит [math]PS[/math].

[math]\triangleleft[/math]

Теорема:

[math]L \subseteq P[/math].

Доказательство:

[math]\triangleright[/math]

Машина Тьюринга, распознающая язык из [math]L[/math], используя не более [math]O(\log n)[/math] памяти, работает не более чем [math]2^{O(\log n)} = poly(n)[/math] времени.

[math]\triangleleft[/math]

Вывод

[math]L \subseteq P \subseteq NP \subseteq PS[/math].

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

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

Теорема:

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

Доказательство:

[math]\triangleright[/math]

Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию [math]I[/math] можно закодировать так: закодировать позицию и содержание рабочей ленты (займет [math]O(\log n)+O(f(n))[/math] памяти), содержание входной ленты (займет [math]O(n)[/math] памяти). Так как [math]f(n) \ge \log n [/math], то размер конфигурации составит [math]O(f(n))[/math]. Пусть [math]L \in 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); 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]O(kf(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]. Головка на входной ленте может быть в одной из n позиций и в одной из [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]\log{2}^{df(n)}=O(f(n))[/math], на каждом уровне рекурсии используется [math]O(f(n))[/math] памяти. Тогда всего эта функция использует [math]O(f(n)^2)[/math] памяти.

[math]\triangleleft[/math]

Следствие

[math]PS=NPS[/math]

Источники

• Michael Sipser. Introduction to the theory of computation.