Теорема Сэвича. Совпадение классов NPS и PS — различия между версиями
(→Определение) |
(→Теорема Сэвича) |
||
Строка 31: | Строка 31: | ||
Для любой <tex>f(n) \ge \log n </tex> справедливо: <tex>\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)</tex>. <br> | Для любой <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> памяти. | + | То есть, если недетерминированная машина Тьюринга может решить проблему, используя <tex>f(n)</tex> памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем <tex>f(n)^2</tex> памяти. |
|proof = | |proof = | ||
Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию <tex>I</tex> можно закодировать так: закодировать позицию и содержание рабочей ленты (займет <tex>O(\log (f(n)))+O(f(n))</tex> памяти), позицию входной ленты (займет <tex>O(\log n)</tex> памяти). | Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию <tex>I</tex> можно закодировать так: закодировать позицию и содержание рабочей ленты (займет <tex>O(\log (f(n)))+O(f(n))</tex> памяти), позицию входной ленты (займет <tex>O(\log n)</tex> памяти). |
Версия 22:10, 31 мая 2012
Содержание
Класс PS
Определение
Определение: |
Определение: |
Связь класса PS с другими классами теории сложности
Теорема: |
. |
Доказательство: |
Рассмотрим любой язык | из . Так как , то существует машина Тьюринга , распознающая за полиномиальное время. Это значит, что не сможет использовать более, чем полиномиальное количество памяти, следовательно .
Теорема: |
. |
Доказательство: |
Рассмотрим любой язык | из . Так как , то существует программа-верификатор , что для каждого слова из (и только для них) существует такой сертификат полиномиальной длины, что допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины. Для этого необходим полиномиальный размер памяти. Из этого следует, что .
Теорема Сэвича
Теорема: |
Для любой справедливо: . То есть, если недетерминированная машина Тьюринга может решить проблему, используя памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем памяти. |
Доказательство: |
Рассмотрим машину Тьюринга с входной и рабочей лентой. Ее конфигурацию можно закодировать так: закодировать позицию и содержание рабочей ленты (займет памяти), позицию входной ленты (займет памяти). Так как , то размер конфигурации составит .Пусть Reach (I, J, k)
if (k = 0)
return (I
J) or (I = J);
else
for (Y) // перебор промежуточных конфигураций
if Reach(I, Y, k-1) and Reach(Y, J, k-1)
return true;
return false;
Эта функция имеет глубину рекурсии , на каждом уровне рекурсии использует памяти для хранения текущих конфигураций.Рассмотрим машину Тьюринга , распознающую язык . Эта машина может иметь конфигураций. Объясняется это следующим образом. Пусть имеет состояний и символов ленточного алфавита. Количество различных строчек, которые могут появиться на рабочей ленте . Головка на входной ленте может быть в одной из n позиций и в одной из на рабочей ленте. Таким образом, общее количество всех возможных конфигураций не превышает .Рассмотрим функцию, которая по заданному слову проверяет его принадлежность к языку : Check (x, L)
for (T) // перебор конфигураций, которые содержат допускающие состояния
if Reach(S, T,
)
return true;
return false;
Если слово принадлежит языку, то оно будет допущено, так как будут рассмотрены все возможные пути допуска. Это обеспечивается указанной нам глубиной рекурсии для функции В итоге функция . И если слово не допускается за шагов (количество всех возможных конфигураций), то оно уже гарантированно не может быть допущено. имеет глубину рекурсии , на каждом уровне рекурсии используется памяти. Тогда всего эта функция использует памяти. |
Следствие
Вывод
.
Известно, что
. Так что хотя бы одно из рассмотренных включений — строгое, но неизвестно, какое. Принято считать, что все приведенные выше включения — строгие.
Источники
- Michael Sipser. Introduction to the theory of computation.