Теорема (Теорема Сэвича). PS = NPS.
Доказательство. Очевидно, что PS ⊆ NPS, поскольку каждая ДМТ является также и НМТ. Доказываем обратное включение: NPS ⊆ PS, т. е. если L допускается НМТ N с ограничением пространства p(n), где p(n)- полином, то L также допускается ДМТ D с ограничением пространства полиномом q(n). Доказательство основано на имитации НМТ N с помощью ДМТ D.
Машина D с помощью рекурсивной процедуры проверяет, что пере - ход от одной МО I к другой – J осуществляется не более, чем за m переходов. По теореме 11.3, если N допускает, то делает это в пределах c1+p(n) шагов, где c – некоторая константа, также и m не превышает cp(n). Получив вход w, машина D исследует тройки вида [I0, J, m ], где I0 – исходное МО, J – заключительное МО машины N, в котором используется не более p(n) клеток. m в каждом вызове рекурсивной процедуры уменьшается в два раза, пока не станет равным 1. Рекурсивных вызовов не более log 2 m, так что элементов [I, J, m/2i] - log 2 m, т. е. log 2 c1+p(n),
или O(p(n)).
Каждый элемент вызова занимает пространство O(p(n)), для записи каждого МО требуется 1+p(n) клеток, а для записи в двоичном виде – log2 c1+p(n), т. е. O(p(n)) клеток.
Таким образом, D использует пространство O(p2(n)), т. е. L допускается ДМТ с полиномиально ограниченным пространством.
Проблема, полная для класса PS.
Проблема P определяется как полная для PS (PS-полная), если :
P ∈ PS. Все языки L из PS полиномиально сводимы к P.Теорема. Пусть P – PS-полная проблема. Тогда :
a) если P∈ P, то P = PS;
b) если P∈ NP, то NP = PS..
Доказательство. Докажем (a). Дано, что P – PS-полная проблема, тогда любой язык L из PS полиномиально, за время q (n), сводим к P. Пусть P∈ P и время работы допускающей ДМТ задается полиномом p(n) .
Цепочка w принадлежит языку L тогда и только тогда, когда, используя сведение, можно получить цепочку x, принадлежащую P. Поскольку сведение занимает время q (⎜w⎟), цепочка x не может быть длинее, чем q (⎜w⎟). Принадлежность x к языку P можно проверить за время p(⎜x⎟), т. е. p(q (⎜w⎟)), полиномиальное относительно ⎜w⎟. Следовательно, для L сушествует полиномиальный по времени алгоритм и L ∈ P. Таким образом, PS ⊆ P. Обратное включение очевидно.
Доказательство (b) аналогично с заменой ДМТ на НМТ.
Примером PS-полной проблемы будет класс “булевых формул с кванторами ” (КБФ). Проблема формулируется так: имеет ли булева формула с кванторами без свободных переменных значение 1 ?
Доказательство основано на идеи теоремы Кука - представления вычисления машины Тьюринга логическими переменными, каждая из которых говорит, имеет ли определенная клетка определенное значение в определенный момент времени. Однако, если в теореме Кука речь шла о полиномиальном времени, поэтому там присутствовало полиномиальное количество переменных, здесь время может быть экспоненциальным, т. е. число МО, а полиномиально пространство вычислений.
Вторая идея - рекурсивной проверки, что одно МО превращается за некоторое, теперь уже экспоненциальное, время m, реализуется благодаря способности самого языка булевых формул с кванторами выражать такого рода факты в пределах полиномиальной длины, даже если m экспоненциально относительно длины входа.
Утверждение разбито на две части : КБФ ∈ PS и каждый язык из PS
полиномиально (по времени) сводим к КБФ.
Теорема. КБФ принадлежит PS.
Доказательство. Рекурсивный процесс вычисления КБФ F может быть организован с использованием магазина, хранимого на ленте машины Тьюринга, как в доказательстве теоремы Сэвича. Пусть n – длина F. Тогда для F создается запись длиной O(n), включающая саму F и пространство для записи обрабатываемых подформул F. Вычисления проводим индукцией по построению формулы F:
Пусть F = F1 + F2 , тогда выполняем следующее : помещаем F1 в ее собственную запись справа от записи F; рекурсивно вычисляем F1; если значением F1 является 1, то возвращаем 1 как значение F; если значение F1 есть 0, то ее запись заменяем записью F2 и рекурсивно вычисляем F2; в качестве значения F возвращаем F2. Пусть F = ∃ x E. Тогда выполняем следующее : подставляем вместо x значение 0 и полученную запись E0 помещаем справа от записи F; рекурсивно вычисляем E0; если значение E0 равно 1, то возвращаем 1 как значение F; если значение E0 равно 0, на место E0 помещаем запись E1, подставляя 1 вместо x, и рекурсивно вычисляем E1; в качестве значения F возвращаем значение E1.Для остальных форм F (F1F2, ¬E, ∀x E) доказательства аналогичны. Для базисного случая, когда F– константа, она возвращается без записей на ленте
Посчитаем объем памяти (ленты). Если F – длины n, на ленте n записей, каждая длиной O(n). Поэтому объем памяти не не превышает O(n2). Таким образом, машина Тьюринга, допускающая КБФ с полиномиально ограниченным пространством. Время работы алгоритма экспоненциально относительно n.
Для сведения языка L из PS к проблеме КБФ воспользуемся идеей доказательства теоремы Кука, где использовались пропозициональные переменные yijA для утверждения, что в j-й позиции i-го МО находится символ A. Однако, поскольку МО экспоненциальное число, воспользуемся квантификацией, чтобы с помощью одного и того же множества переменных представлять много различных МО.
Теорема. Проблема КБФ PS-полна.
Доказательство. Пусть L – язык из PS, допускаемый недетерминированной машиной M, которая на входе длины n использует не более p(n) клеток. По теореме Сэвича существует константа “c”, для которой M допускает вход за c 1+ p(n) переходов (если допускает). Опишем, как за полиномиальное время по входу w длины n построить КБФ E без свободных переменных, имеющее значение 1 тогда и только тогда, когда
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
