dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 99
Текст из файла (страница 99)
Преобразование в одноленточную НМТ может возвести время в квадрат, так чтоодноленточной НМТ будет достаточно времени O(n4).Теперь нужно доказать трудную часть — что для произвольного языка L из NP существует полиномиальное сведение L к ВЫП. Можно предположить, что существует некоторая одноленточная НМТ M и полином p(n), для которого M обрабатывает вход длинойn не более, чем за p(n) шагов вдоль любой ветки. Далее, ограничения, доказанные в теореме 8.12 для ДМТ, можно аналогично доказать и для НМТ. Поэтому можно предположить, что M никогда не печатает пробела и никогда не сдвигает головку левее ее исходной позиции.Итак, если M допускает вход w, и |w| = n, то существует последовательность переходов M со следующими свойствами.2.α0 — исходное МО M со входом w.α0 |− α01 |− L |− αk, где k ≤ p(n).3.αk — МО с допускающим состоянием.1.10.2. ÏÅÐÂÀß NP-ÏÎËÍÀß ÏÐÎÁËÅÌÀСтр.
439439Каждое αi не содержит пробелов (за исключением тех αi, которые заканчиваются состоянием и пробелом) и располагается вправо от исходной позиции головки —крайнего слева входного символа.4.Стратегия построения формулы вкратце такова.1.Каждое αi может быть записано как последовательность символов Xi0Xi1…Xi,p(n) длиной p(n) + 1. Один из них — состояние, а остальные p(n) — ленточные символы. Какобычно, предположим, что множества состояний и ленточных символов не пересекаются, так что можно отличить, какое из Xij является состоянием, и указать, где находится головка.
Отметим, что нет надобности представлять символы, расположенные справа от первых p(n) символов на ленте, поскольку, если M гарантированно останавливается, сделав не более p(n) переходов, то на переходы M эти символысправа не влияют.2.Для описания последовательности МО в терминах булевых переменных введем переменные yijA, которые представляют утверждения вида Xij = A. Здесь i и j — целыеиз интервала от 0 до p(n), а A — либо ленточный символ, либо состояние.3.Условие того, что последовательность МО представляет допускание, записывается ввиде булевой формулы, выполнимой тогда и только тогда, когда M допускает w в результате последовательности не более чем p(n) переходов. Удовлетворяющая подстановка “характеризует” МО, т.е. yijA истинна тогда и только тогда, когда Xij = A.Для гарантии того, что полиномиальное сведение L(M) к ВЫП корректно, эта формула записывается так, чтобы отражать следующие свойства вычисления.i.
Правильный старт — исходное МО есть q0w с последующими пробелами.ii. Правильные переходы (т.е. согласующиеся с правилами МТ) — каждоепоследующее МО получается из предыдущего путем выполнения одного из возможных законных переходов M.iii. Правильный финиш — существует МО с допускающим состоянием.Прежде, чем точно описать построение нашей булевой формулы, рассмотрим несколько деталей.• Во-первых, по построению МО заканчивается там, где начинается бесконечный“хвост” из пробелов. Однако, имитируя вычисление за полиномиальное время,удобнее считать, что все МО имеют одну и ту же длину p(n) + 1. Поэтому в МОможет присутствовать хвост из пробелов.• Во-вторых, удобно считать, что все вычисления происходят в точности за p(n)переходов (и, следовательно, имеют p(n) + 1 МО), даже если допускание происходит раньше. Следовательно, всякому МО с допускающим состоянием позволено быть собственным преемником, т.е., когда α содержит допускающее состояние, разрешен “переход” α |− α.
Таким образом, можно предполагать, что если440Стр. 440ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛсуществует допускающее вычисление, то αp(n) имеет допускающее состояние, иэто все, что нужно проверить в условии (iii).На рис. 10.4 представлен общий вид полиномиального вычисления M. Строки соответствуют последовательности МО, а столбцы — это клетки на ленте, которые могут использоваться при вычислении. Заметим, что число ячеек на рис. 10.4 равно (p(n) + 1)2. Крометого, число различных значений переменных, представляющих ячейки, конечно и зависит только от M; оно равно сумме числа состояний и числа ленточных символов M.МО01α0X00X01X0,p(n)α1X10X11X1,p(n)αiαi+1αp(n)Xp(n),0......Xi,j–1Xi,jXi,j+1Xi+1,j–1Xi+1,jXi+1,j+1Xp(n),1p(n)Xp(n),p(n)Рис. 10.4. Построение массива данных о последовательности МОПриведем теперь алгоритм построения булевой формулы EM,w по M и w.
Общий видEM,w — S ∧ N ∧ F, где формулы S, N и F говорят о том, что M совершает правильныйстарт, переходы и финиш.Ïðàâèëüíûé ñòàðòСимвол X00 должен быть начальным состоянием q0 машины M, символы с X01 поX0n — образовывать цепочку w (n — ее длина), а оставшиеся X0j — быть пробелами B,т.е. если w = a1a2…an, тоS = y00q0 ∧ y01a1 ∧ y02a2 ∧ L ∧ y0nan ∧ y0,n+1,B ∧ y0,n+2,B ∧ L ∧ y0,p(n),B.Безусловно, по данным M и w можно записать S на второй ленте многоленточной МТ завремя O(p(n)).Ïðàâèëüíûé ôèíèøПоскольку предполагается, что допускающее МО повторяется до бесконечности, то допускание M эквивалентно присутствию допускающего состояния в αp(n). Напомним, что попредположению M является такой НМТ, которая, если допускает, то делает это в пределах10.2.
ÏÅÐÂÀß NP-ÏÎËÍÀß ÏÐÎÁËÅÌÀСтр. 441441p(n) шагов. Таким образом, F есть логическое ИЛИ формул Fj для j = 0, 1, …, p(n), где Fjутверждает, что Xp(n),j — допускающее состояние, т.е. Fj есть yp(n),j,a1 ∨ yp(n),j,a2 ∨ L ∨ yp(n),j,ak,где a1, a2, …, ak — все допускающие состояния M. ТогдаF = F0 ∨ F1 ∨ ... ∨ Fp(n).Отметим, что в каждом из Fi используется постоянное число символов, которое зависитот M, а не от длины n входа w. Поэтому F имеет длину O(p(n)). Более важно то, что время,необходимое для записи F по данным коду M и цепочке w, полиномиально зависит от n. Вдействительности, формулу F можно записать на многоленточной МТ за время O(p(n)).Ïðàâèëüíûå ïåðåõîäûНамного сложнее убедиться, что M правильно выполняет переходы. Формула N будетлогическим И формул Ni, где i = 0, 1, …, p(n) – 1, и каждое Ni строится так, чтобы αi+1было одним из МО, в которые можно перейти из αi по правилам M.
Чтобы понять, какследует записать Ni, рассмотрим символ Xi+1,j на рис. 10.4. Символ Xi+1,j всегда можноопределить, зная:а) три символа над ним, т.е. Xi,j–1, Xi,j и Xi,j+1;б) выбор перехода НМТ M, если один из этих символов есть состояние в αi.Запишем Ni как логическое И формул Aij ∨ Bij, где j = 0, 1, …, p(n).• Формула Aij говорит о том, что:а) состояние МО αi находится в позиции j, т.е. Xij — состояние;б) если Xij — состояние и Xi,j+1 — обозреваемый символ, то существует выбортакого перехода M, который преобразует последовательность символовXi,j–1XijXi,j+1 в Xi+1,j–1Xi+1,jXi+1,j+1.
Заметим, что если Xij — допускающее состояние, то возможен только “выбор”, при котором переход вообще не совершается, поэтому все последующие МО совпадают с первым, приведшим к допусканию.• Формула Bij говорит о том, что:а) состояние МО αi достаточно далеко от Xij, так что оно не может влиять наXi+1,j (ни один из символов Xi,j–1, Xij, Xi,j+1 не является состоянием);б) Xi+1,j = Xij.Формулу Bij записать легче, чем Aij. Пусть q1, q2, …, qm — состояния, а Z1, Z2, …, Zr —ленточные символы. ТогдаBij = (yi,j–1,Z1 ∨ yi,j–1,Z2 ∨ L ∨ yi,j–1,Zr) ∧(yi,j,Z1 ∨ yi,j,Z2 ∨ L ∨ yi,j,Zr) ∧(yi,j+1,Z1 ∨ yi,j+1,Z2 ∨ L ∨ yi,j+1,Zr) ∧(yi,j,Z1 ∧ yi+1,j,Z1) ∨ (yi,j,Z2 ∧ yi+1,j,Z2) ∨ L ∨ (yi,j,Zr ∧ yi+1,j,Zr).442Стр.
442ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛПервая, вторая и третья строчки в Bij соответственно выражают, что Xi,j–1, Xij и Xi,j+1 —ленточные символы. Последняя строчка выражает равенство Xi+1,j = Xij; в ней перечисляются все возможные ленточные символы Z, и говорится, что обе переменные — это либоZ1, либо Z2 и т.д.Существует два важных частных случая: j = 0 и j = p(n).
В первом нет переменных yi,j–1,Z,а во втором — переменных yi,j+1,Z. Однако нам известно, что головка никогда не сдвигается влево от своего исходного положения и что ей не хватит времени, чтобы сдвинутьсяболее чем на p(n) клеток вправо от исходной. Поэтому из Bi0 и Bi,p(n) можно выброситьнекоторые члены. Выполните это упрощение самостоятельно.Рассмотрим теперь формулы Aij. Эти формулы отражают все возможные связи междусимволами Xi,j–1, Xij, Xi,j+1, Xi+1,j–1, Xi+1,j и Xi+1,j+1 в прямоугольниках размером 2¥3 из массива (см.
рис. 10.4). Подстановка символов в каждую из этих шести переменных являетсяправильной, если:а) Xij есть состояние, а Xi,j–1 и Xi,j+1 — ленточные символы;б) состоянием является только один из Xi+1,j–1, Xi+1,j и Xi+1,j+1;в) существует переход M, объясняющий, как Xi,j–1XijXi,j+1 превращается вXi+1,j–1Xi+1,jXi+1,j+1.Таким образом, для этих шести переменных существует лишь конечное число правильных подстановок символов. Пусть Aij будет логическим ИЛИ членов, по одному для каждого множества из шести переменных, образующего правильную подстановку.Предположим, что переход M обусловлен тем, что δ(q, A) содержит (p, C, L).
Пусть D —некоторый ленточный символ M. Тогда Xi,j–1XijXi,j+1 = DqA и Xi+1,j–1Xi+1,jXi+1,j+1 = pDC —одна из правильных подстановок. Заметим, как эта подстановка отражает изменение МО,вызванное данным переходом M. Член, отражающий эту возможность, имеет видyi,j–1,D ∧ yi,j,q ∧ yi,j+1,A ∧ yi+1,j–1,p ∧ yi+1,j,D ∧ yi+1,j+1,C.Если же δ(q, A) содержит (p, C, R), т.е. переход такой же, но головка сдвигается вправо, то соответствующая правильная подстановка — это Xi,j–1XijXi,j+1 = DqA и Xi+1,j–1Xi+1,jXi+1,j+1 = DCp.Соответствующий член имеет видyi,j–1,D ∧ yi,j,q ∧ yi,j+1,A ∧ yi+1,j–1,D ∧ yi+1,j,C ∧ yi+1,j+1,p.Формула Aij есть логическое ИЛИ всех правильных членов.
В особых случаях, когда j = 0 и j = p(n), нужно внести некоторые изменения, чтобы учесть отсутствие переменных yijZ при j < 0 или j > p(n), как для Bij.Наконец,Ni = (Ai0 ∨ Bi0) ∧ (Ai1 ∨ Bi1) ∧ L ∧ (Ai,p(n) ∨ Bi,p(n))иN = N0 ∧ N1 ∧ L ∧ Np(n)–1.10.2. ÏÅÐÂÀß NP-ÏÎËÍÀß ÏÐÎÁËÅÌÀСтр. 443443Несмотря на то что формулы Aij и Bij могут быть очень громоздкими (если M имеетмного состояний и/или ленточных символов), их размер представляет собой константу ине зависит от длины входа w.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
