Рассмотрим класс проблем, включающий классы P и NP. Этот класс определяется машинами Тьюринга с полиномиальной емкостной сложностью (время работы значения не имеет). Дальше будет показано, что классы языков PS и NPS, допускаемые соответственно детерминированными и недетерминированными машинами Тьюринга с полиномиально ограниченным объемом памяти (используемой рабочей лентой), совпадают.
В полиномиальном пространстве существуют полные проблемы P в том смысле, что все проблемы данного класса полиномиально сводимы к P. Таким образом, если PÎ P или PÎ NP, то все языки машин Тью- ринга с полиномиально ограниченной емкостью принадлежат P или NP, соответственно. Примером такой проблемы будет язык “булевых формул с кванторами” (КБФ).
Классы PS и NPS.
Включения P Í PS и NP Í NPS очевидны. Доказав, что PS = NPS,, получим :P Í NP Í PS..
Другой интересный факт, касающийся новых классов, тот, что PS содержит только рекурсивные языки.
Теорема.Если M – машина Тьюринга с полиномиально ограниченным пространством, где p(n)- ограничивающий полином, то существует константа c, что M допускает вход длины n за O(с1+ p(n) ) переходов.
Доказательство. В обосновании существования “c” используется то, что у машины Тьюринга с ограниченным пространством имеется лишь ограниченное число МО. Если t – число ленточных символов, а s – число состояний машины M, то число различных МО машины, использующей p(n) клеток, не более s × p(n) × t p(n) , т.е. можно выбрать одно из s состо- яний, поместить считывающую головку в одну из p(n) позиций и заполнить p(n) клеток любой из t p(n) последовательностей ленточных символов.
Положим c = s + t и вычислим бином (t + s)1 + p(n) =
1 + t 1 + p(n) + (1 + p(n))×s× t p(n) + …, где второе слагаемое не меньше
p(n)×s× t p(n), что доказывает, что c 1 + p(n) не меньше числа возможных конфигураций M.
Если машина M допускает вход длины n, то она совершает последовательность конфигураций без повторений. Следовательно, M допускает, совершив не более c 1 + p(n) переходов (количество различных МО). “
Теорема.Если L – язык из PS (NPS), то L допускается детерминирован- ной (недетерминированной) машиной Тьюринга с полиномиально ограниченным пространством, которая для некоторого полинома q(n) и константы “c” останавливается, сделав не более с q (n) переходов.
Доказательство. Пусть язык L допускается детерминированной машиной Тьюринга M1 (для НМТ доказательство аналогично), имеющей полиномиальное ограничение пространства p(n). По теореме 11.3, если M1 допускает вход w, то делает около c 1 + p(êwê) шагов.
Построим машину M2, имеющую две ленты. На первой ленте M2 имитирует M1, а на второй ведет счет шагов до c 1 + p(êwê) и останавливается, не допуская, если это число достигнуто. Поскольку машиной M1 используется не более p (êw ê) клеток, M2 использует также не более
p (êw ê) клеток первой ленты.
Преобразуя M2 в одноленточную машину M3, можно гарантировать, что M3 использует не более 1 +p (êw ê) клеток и время работы O(c2 p(êwê)).
Машина M3 совершает не более d×c 2 p(êwê) переходов для некоторой константы d, поэтому можно выбрать q(n) = 2 p(n) + log c d, где n – длина входа. Тогда M3 совершает не более cq(n) шагов. M2 всегда останавливается, поэтому то же делает и M3. M1 допускает L, поэтому M2 и M3 допускают L. Таким образом, M3 удовлетворяет теореме. “
Теорема (Теорема Сэвича). 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-полная), если :
1. P Î PS.
2. Все языки 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:
1. Пусть F = F1 + F2 , тогда выполняем следующее :
a) помещаем F1 в ее собственную запись справа от записи F;
b) рекурсивно вычисляем F1;
c) если значением F1 является 1, то возвращаем 1 как значение F;
d) если значение F1 есть 0, то ее запись заменяем записью F2 и рекурсивно вычисляем F2;
e) в качестве значения F возвращаем F2.
2. Пусть F = $ x E. Тогда выполняем следующее :
a) подставляем вместо x значение 0 и полученную запись E0 помещаем справа от записи F;
b) рекурсивно вычисляем E0;
c) если значение E0 равно 1, то возвращаем 1 как значение F;
d) если значение E0 равно 0, на место E0 помещаем запись E1, подставляя 1 вместо x, и рекурсивно вычисляем E1;
e) в качестве значения 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 тогда и только тогда, когда
w Î L(M).
Для записи E потребуется ввести полиномиальное число переменных yjA, утверждающих, что j-я позиция представляемого МО содержит символ A – ленточный или состояние M (j может изменяться от 0 до p(n)).
Предположим, что пропозициональные переменные разных МО различны. Но поскольку разных МО полиномиальное число, общее количество пропозициональных переменных полиномиально.
Обозначимкванторную приставку ($x1$x2…$xm), где x1, x2,…,xm – все пропозициональные переменны МО I как ($I); аналогично для квантора всеобщности – ("). КБФ примет вид : ($I0) ($If) (S & N & F), где
1. I0 и If - переменные МО, представляющие начальное и допускающее М, соответственно.
2. S – выражение, говорящее, что I0 является начальным МО машины M на входе w.
3. N – выражение, говорящее о переходах M при преобразовании I0 к If.
4. F – выражение, говорящее, что If является допускающим МО.
О каждой формуле в деталях:
S – конъюнкция литералов; каждый литерал – одна из переменных МО. Литерал yjA входит в I0 , если в j-й позиции начального МО с входом w находится символ A, в противном случае в I0 входит Ø yjA.
Таким образом, если w = a 1a 2…a n , то без отрицания в МО I0 входят y0q 0 , y1a1 , y2a2 ,…, ynan и все yj B для j = n+1, n+2,…, p(n), где q0 – начальное состояние и B = L, а все остальные переменные МО I0 - с отрицаниями.
If - допускающее МО, если содержит заключительное (допускающее) состояние. F – дизъюнкция переменных yj A, выбранных из пропозициональных переменных МО If , для которых A является допускающим состоянием. Позиция j произвольна.
N – строится с помощью метода, позволяющего удвоить число рассматриваемых переходов, добавив лишь O(p(n)) символов и затратив O(p(n)) времени. Равенством I = J обозначим конъюнкцию выражений
( yj A zj A +Øyj A Øzj A), где j изменяется от 0 до p(n), а A – любой ленточный символ или состояние M, МО I состоит из переменных yjA и
J - из переменных z jA.
Ni (I, J) - означает, что переход от МО I к МО J занимает не более i переходов, обозначается I ├ i J, i = 1,2,4,… . В этих выражениях свободны только переменные I и J, остальные переменные связаны.
Базис. Для i = 1 выражение Ni (I, J) устанавливает, что I = J или I ├ 1 J, т.е. N1(I, J) есть дизъюнкция этих утверждений. N1 (I, J) записывается за время O(p(n)).
Индукционный шаг. По Ni строим N2i . Корректный способ записи N2i состоит в том, чтобы в выражении записывать одну копию Ni , подставляя как (I, K), так и (K, J) в одно и то же выражение. Таким образом, в N2i (I, J) используется одно подвыражение Ni (P, Q). N2i (I, J) утверждает, что существует МО K, при котором для всех МО P и Q выполняется хотя бы одно из следующих условий :
1) (P, Q) ¹ (I, K) и (P, Q) ¹ (K, J); 2) Ni (P, Q) - истинно.
Иными словами, Ni (I, K) и Ni (K, J) истинны, а для других пар МО
(P, Q) истинность Ni (P, Q) не имеет значения. Итак, КБФ имеет вид :
N2i (I, J) = ($K)("P)("Q)(N i (P, Q) Ú (Ø (I = P & K = Q) & Ø (K = P & J = Q))).
На запись N2i (I, J) уходит время, необходимое для записи N i , а также O(p(n)) для дополнительной работы.
Чтобы завершить построение N, нужно записать Nm для наименьшего m, которое является степенью 2 и не меньше c1+ p(n) – максимально возможного числа переходов, совершаемых M до заключительного (допуска- ющего) состояния. Количество применений шага индукции, описанного выше, равно log2 (c1+ p (n) ), или O(p(n)). Поскольку каждое исполнение шага индукции требует O(p(n)) времени, то N строится за время O(p2(n)).
Завершение доказательства теоремы. Выше было показано, как преобразовать вход w в КБФ - ($I0) ($If) (S & N & F) за время, полиномиальное относительно çw÷. Было доказано, что выражения S, N, F - истинны тогда и только тогда, когда их свободные переменные представляют МО I0 и If , являющиеся соответственно начальным и заключительным МО в вычислениях машины M на входе w. Таким образом, данная КБФ имеет значение 1 тогда и только тогда, когда M допускает w.“
