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

Класс PS

Определение

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

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