Главная Промышленная автоматика.

3. С утверждает, что в каждый момент времени t машина М находится в одном и только одном состоянии:

С= П U(S<l,t>,S<2,t>.....S<s,t».

0</<р(я)

Так как число состояний s машины М постоянно, то С имеет длину Oipin)).

4. D утверждает, что в любой момент времени / можно изменить содержимое не более чем одной клетки

D = Д [(С<i, }, t>C<i, j,t+l» + H<i, t>].

Формула (C<t, /, f>C<i, j, <+1>)+Я<1, /> утверждает, что либо

(а) в момент t головка обозревает клетку i, либо

(б) /-й символ записан в клетке i в момент t+1 тогда и только тогда, когда он был записан там в момент /.

Поскольку А а В утверждают, что в момент t головка обозревает только одну клетку и клетка i содержит лишь один символ, то в момент времени t либо головка обозревает клетку i, либо содержимое клетки i не меняется. Если раскрыть значение знака =, то длина D будет 0{р{п)).

5. Е утверждает, что очередное МО машины М получается из предыдущего одним переходом, разрешаемым функцией переходов б машины М. Пусть означает одно из следующих утверждений:

(а) в момент t клетка / не содержит символа /,

(б) в момент t головка не обозревает клетку /,

(в) в момент / машина М не находится в состоянии k,

(г) очередное МО машины М получается из предыдущего переходом, разрешаемым функцией переходов машины М.

Тогда где

Eijkt = C<i, j, ky+-iH<i, /> + -iS<A:, /> +

+ 2[C<i, ic, t + \>S<kt, t + \yHK.il, t + b\.

Здесь / пробегает по всем шагам машины М, возможным в случае, когда М обозревает символ Xj в состоянии q,. Иными словами, для каждой тройки iq, X, dy из 6{q, Xj) существует одно значение /, для которого Xj=X, qk~q и число равно i-1, i или i+\ ч зависимости от d: сдвигается ли головка влево (d=L, ii=i-1),

) х=у означает ху+ху (х тогда и только тогда, когда у).



вправо (d==R, i,=i+l) или остается на месте (d=S, ii=i). Здесь 6 - функция переходов для М. Поскольку машина М недетермини-рованна, то таких троек (q, X, d) может быть несколько, но во всяком случае их число конечно. Таким образом, Euit имеет ограниченную длину, не зависящую от п. Поэтому £ имеет длину 0(р(л)).

6. F утверждает, что выполнены начальные условия:

f = 5<1,0>Я<1,0> П C<f,/,.,0> П C<t, 1,0>.

1<1<п п<{<р{п)

где S<1, 0> утверждает, что М в момент /=0 находится в состоянии 1, которое мы считаем начальным; Я<1, 0> утверждает, что М в момент /=0 обозревает самую левую клетку ленты; II C<i, ji, 0> утверждает, что первые п клеток вначале

к.к.П

содержат входную цепочку w\ Ц C<i, 1, 0> утверждает, что

я<1<р (п)

остальные клетки вначале пусты. Мы считаем, что пустым символом является Xi. Очевидно, что F имеет длину 0(р(л)).

7. G утверждает, что М в конце концов приходит в заключительное состояние. Поскольку мы потребовали, чтобы машина М оставалась в заключительном состоянии после того, как оно достигнуто, то G=S<s, р{п)у. Мы считаем, что заключительным состоянием является q,.

Булева формула - это произведение ABCDEFG. Поскольку каждый из семи сомножителей состоит не более чем из 0(р(/г)) символов, сама формула Wo также состоит не более чем из 0(р (п)) символов. Так как мы считали каждую пропозициональную переменную за один символ, а в действительности переменные представляются цепочками длины O(log /г), то на самом деле границей на а;о будет 0(р(/г) log л), а это не превосходит слр (л), где с - некоторая постоянная. Таким образом, длина цепочки Wo полиномиально зависит от длины цепочки w. Должно быть ясно, что если даны цепочка W и полином р, то формулу Wo можно записать за время, пропорциональное ее длине.

По данной допускающей последовательности МО Qo, Qi,. . ., Q, можно, очевидно, найти такое присваивание значений О и 1 пропозициональным переменным С<г, /, ty, S<k, ty и Я<г, ty, что Wo примет значение истина. Обратно, если дано присваивание значений переменным формулы Wo, при котором она становится истинной, то легко найти допускающую последовательность МО. Таким образом, формула Wo выполнима тогда и только тогда, когда М допускает цепочку w.

Мы не наложили на язык L, допускаемый машиной М, никаких ограничений, кроме того, что он принадлежит классу Ж9. Поэтому мы показали, что любой язык из полиномиально трансформи-



руем в задачу выполнимости булевых формул. Отсюда заключаем, что задача выполнимости NP-полна. □

На самом деле мы доказали больше, чем утверждается в теореме 10.3. Говорят, что булева формула находится в конъюнктивной нормальной форме (КНФ), если она представляет собой произведение сумм литералов, где каждый литерал имеет вид х или -\х для некоторой переменной х. Например, (Хг+ХгХг+Хг+Хз) находится в КНФ, а XiXi+Xa нет. Формула Wo, построенная в доказательстве теоремы 10.3, практически находится в КНФ - ее можно представить в КНФ, увеличив длину не более чем в постоянное число раз.

Следствие. Задача выполнимости булевых формул, находяиихся в КНФ, НР-полна.

Доказательство. Достаточно показать, что каждая из формул А,. . ., G, построенных в доказательстве теоремы 10.3, либо уже находится в КНФ, либо может быть преобразована в такую с помощью правил булевой алгебры, причем ее длина увеличится не более чем в постоянное число раз. Формула U, определенная равенством (10.1), уже находится в КНФ. Отсюда следует, что А, В и С тоже находятся в КНФ. Рид тривиально находятся в КНФ, поскольку F и G - произведения литералов.

D - формула вида (je=«/)+z. Если раскрыть знак =, получится выражение

ху + ху + г, (10.2)

эквивалентное

{х+у + г)(х + у + г). (10.3)

Подставив (10.3) вместо всех вхождений (10.2) в D, получим формулу, эквивалентную исходной, но находящуюся в НКФ и превосходящую исходную формулу по длине не более чем в 2 раза.

Наконец, Е - произведение формул .Ес Поскольку длины всех Eijt ограничены независимо от п, каждую формулу Etjt можно преобразовать в формулу в КНФ, причем ее длина не будет зависеть от п. Поэтому преобразование формулы Е в формулу в КНФ увеличивает ее длину не более чем в постоянное число раз.

Итак, формулу Wo можно представить в КНФ, увеличив ее длину не более чем в постоянное число раз. □

Мы только что показали, что задача выполнимости формул в КНФ NP-полна. Можно показать, что даже при более жестких ограничениях на вид формулы задача выполнимости булевых формул также NP-полна. Говорят, что формула находится в k-конъюнк-тивной нормальной форме (-КНФ), если она представляет собой произведение сумм, состоящих не более чем из k литералов. Задача А-выполнимости состоит в выяснении выполнимости формулы, нахо-





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 [138] 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.002