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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «='''Класс ''' ''PS''= == Определение == {{Определение |definition='''Класс''' <tex>PS(PSPACE)</tex> {{---}} класс язык...»)
(нет различий)

Версия 02:21, 17 апреля 2012

Класс 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] памяти.