26
правок
Изменения
Нет описания правки
=Теорема Сэвича=
{{Теорема
|statement =
Для любой <tex>f(n) \ge \log n </tex> справедливо: <tex>\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)</tex>. <br>
То есть, если недетерминированная машина Тьюринга может решить проблему , используя <tex>f(n)</tex> памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем <tex>f(n)^2</tex> памяти.
|proof =
Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию <tex>I</tex> можно закодировать так: закодировать позицию и содержание рабочей ленты (займет <tex>O(\log (f(n)))+O(f(n))</tex> памяти), содержание позицию входной ленты (займет <tex>O(\log n)</tex> памяти).
Так как <tex>f(n) \ge \log n </tex>, то размер конфигурации составит <tex>O(f(n))</tex>.
Пусть <tex>L \in \mathrm{NSPACE}(f(n))</tex>. Тогда существует недетерминированная машина Тьюринга, распознающая этот язык.<br>Рассмотрим вспомогательную функцию <tex>Reach(I, J, k)</tex>, вычисляющую возможность перехода из конфигурации <tex>I</tex> в конфигурацию <tex>J</tex> за не более, чем <tex>2^k</tex> переходов:
'''Reach''' (I, J, k):
'''if''' (k = 0)
'''return''' (I <tex>\vdash</tex> J) or (I = J); // запись (I <tex>\vdash</tex> J) означает возможность перехода МТ из конфигурации I в конфигурацию J за один шаг
'''else'''
'''for''' (Y) // перебор промежуточных конфигураций
'''if''' Reach(I, Y, k-1) and Reach(Y, J, k-1)
'''return''' true; '''return''' false;
Эта функция имеет глубину рекурсии <tex>O(k)</tex>, на каждом уровне рекурсии использует <tex>O(f(n))</tex> памяти для хранения текущих конфигураций. Тогда всего функция использует <tex>O(kf(n))</tex> памяти.
Рассмотрим машину Тьюринга <tex>Mm</tex>, распознающую язык <tex>L</tex>. Эта машина может иметь <tex>2^{df(n)}</tex> конфигураций. Объясняется это следующим образом. Пусть <tex>Mm</tex> имеет <tex>c</tex> состояний и <tex>g</tex> символов ленточного алфавита. Количество различных строчек, которые могут появиться на рабочей ленте <tex>g^{f(n)}</tex>. Головка на входной ленте может быть в одной из <tex>n </tex> позиций и в одной из <tex>f(n)</tex> на рабочей ленте. Таким образом, общее количество всех возможных конфигураций не превышает <tex>cnf(n)g^{f(n)}=2^{\log c + \log n + \log (f(n)) + f(n) \log g}=2^{O(f(n))}</tex>.
Рассмотрим функцию, которая по заданному слову <tex>x</tex> проверяет его принадлежность к языку <tex>L</tex>:
'''Check''' (x, L):
'''for''' (T) // перебор конфигураций, которые содержат допускающие состояния
'''if''' Reach(S, T, <tex>\log \left(2^{df(n)}\right)</tex>)
'''return''' true; '''return''' false;
Если слово принадлежит языку, то оно будет допущено, так как будут рассмотрены все возможные пути допуска. Это обеспечивается указанной нам глубиной рекурсии для функции <tex>Reach</tex>. И если слово не допускается за <tex>2^{df(n)}</tex> шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено.
В итоге функция <tex>Reach</tex> имеет глубину рекурсии <tex>\log{2}^{df(n)}=O(f(n))</tex>, на каждом уровне рекурсии используется <tex>O(f(n))</tex> памяти. Тогда всего эта функция использует <tex>O(f(n)^2)</tex> памяти.
}}
==Следствие==
<tex>\mathrm{PS}=\mathrm{NPS}</tex> =Вывод=<tex>\mathrm{L} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PS} = \mathrm{NPS}</tex>. Известно, что <tex>\mathrm{L} \neq \mathrm{PS} </tex>. Так что хотя бы одно из рассмотренных включений {{---}} строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения {{---}} строгие. = См. также =*[[Класс PS. Связь класса PS с другими классами теории сложности]]
=Источники=
* Michael Sipser. Introduction to the theory of computation.
[[Категория: Теория сложности]]
