Теорема Сэвича. Совпадение классов NPS и PS
Версия от 19:45, 13 мая 2012; 194.85.161.2 (обсуждение)
Класс 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.