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

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

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

Теорема:
Для любой [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.