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

дящейся в -КНФ. Для k=l и 2 известны детерминированные алгоритмы полиномиальной сложности, проверяющие -выполнимость. Ситуация (по-видимому) изменяется при =3, как видно из следующей теоремы.

Теорема 10.4. Задача 3-выполнимости NP-полна.

Доказательство. Покажем, что выполнимость формул в КНФ полиномиально трансформируема в 3-выполнимость. В данном произведении сумм заменим каждую сумму {Х1+Хг+. . .+х), Л4, на

(Jf, -f Jf а + «/i) (Хз +У,+У2)(х+Уг-Уз) -

• • + у k-i + Ук-а) (.Xk-i + Хк+ Ук-а), (10.4)

где «/2,. . ., «/ft 3-новые переменные. Например, для А=4 выражение (10.4) принимает вид (,Xi-\-X2-\-yi){Xa-\-Xi-\-yi).

Присвоить значения новым переменным так, чтобы подставляемая формула приняла значение 1, можно тогда и только тогда, когда один из литералов Хи Х2,. .., Xf имеет значение 1, т. е. тогда и только тогда, когда исходная формула принимает значение 1. Допустим, что Xi=\. Тогда положим У]=\ для /t-2 и Уз-О для j>i-2. Подставляемая формула принимает значение 1. Обратно, допустим, что при некоторых значениях переменных yt подставляемая формула принимает значение 1. Если yi-0, то одна из переменных Xi и Ха должна иметь значение 1. Если «/-3=1, то одна из переменных x i и jc должна иметь значение 1. Если «/i=l и «/ft 3=0, то для некоторого i, lik-4, выполнены оба равенства «/г = 1 и «/i-n=0, откуда следует, что переменная Xi+i должна иметь значение 1. В любом случае некоторая переменная Х[ должна иметь значение 1.

Длина формулы, получаемой в результате описанной выше замены, превосходит длину исходной формулы не более чем в постоянное число раз. Таким образом, по данной формуле Е в КНФ можно найти, применяя описанное выше преобразование к каждой сумме, формулу Е в 3-КНФ, выполнимую тогда и только тогда, когда выполнима исходная формула. Более того, легко показать, что Е можно найти за время, пропорциональное длине формулы Е, выполняя преобразования очевидным образом. □

10.5. ЕЩЕ НЕСКОЛЬКО NP-ПОЛНЫХ ЗАДАЧ

Теперь приступим к доказательству того, что каждая из задач, упомянутых в теореме 10.2, NP-полна. Для этого покажем, что в нее прямо или косвенно преобразуется выполнимость. Дерево на рис. 10.6 иллюстрирует последовательность преобразований, которые мы в действительности будем применять. Если Р - отец для




wwag покрытие

Рис. 10.6. Последовательность преобразований для различных трудных задач.

Р на рис. 10.6, то мы покажем, что задача Р полиномиально трансформируема в Р.

Теорема 10.5. Задача КНФ-выполнимости полиномиально трансформируема в задачу о клике. Поэтому задача о клике NP-полна.

Доказательство. Пусть Р=Рхр2. . .Р - формула в КНФ, где Fi - сомножители; каждая формула f, имеет вид {Хц-\-•\-Xi2-\- . .+Jeift(), где Xjj -литерал. Построим неориентированный граф 0=(У, Е), узлами которого служат пары целых чисел [i, j] для lt(7 и l/j. Первая компонента такой пары представляет сомножитель, а вторая - литерал, входящий в него. Таким образом, каждый узел графа естественным образом соответствует конкретному вхождению в конкретный сомножитель.

Ребрами графа G служат пары ([t, 1. 1). Для которых ik и Х1]Фх,1. Неформально, узлы [i, /] и [k, I] смежны в G, если они соответствуют различным сомножителям и можно так присвоить значения переменным из литералов Хц и Xfi, чтобы оба литерала приняли значения 1 (тем самым давая значение 1 формулам Fi и f ft). Иными словами, либо Хц=х1, либо переменные, входящие в литералы Хц и xi, различны.

Число узлов в G, очевидно, меньше длины формулы F, а число ребер не превосходит квадрата числа узлов. Поэтому граф G можно закодировать в виде цепочки, длина которой ограничена полиномом от длины формулы F, и, что еще важнее, такой код можно найти за время, ограниченное полиномом от длины F. Мы покажем, что G содержит 9-клику тогда и только тогда, когда формула F выполнима. Отсюда будет следовать, что по данному алгоритму, решающему задачу о клике за полиномиально ограниченное время, можно по-



строить алгоритм с полиномиально ограниченным временем работы для задачи КНФ-выполнимости, построив по f графО, содержащий -клику тогда и только тогда, когда формула F выполнима. Итак, покажем, что для того, чтобы граф G содержал -клику, необходимо и достаточно, чтобы формула F была выполнима.

Достаточность. Пусть формула F выполнима. Тогда существует набор значений переменных, состоящий из нулей и единиц, при котором F=\. При этом наборе каждый сомножитель формулы F принимает значение 1. Каждый сомножитель Fi содержит по меньшей мере один литерал, принимающий значение 1. Пусть таким литералом в Ft будет Xim..

Мы утверждаем, что множество узлов {[i, /nJlli} образует 9-клику. Если бы это было не так, то нашлись бы такие i и /, что ii=j и узлы и, mi] и [/, mj] не соединены ребром. Отсюда следовало бы, что Xim=Xjm (по определению множества ребер графа G). Но это невозможно, поскольку Ximi=Xjmj= 1 в силу выбора переменных

Xlmi

Необходимость. Пусть G содержит -клику. Первые компоненты узлов, составляющих такую клику, должны быть различны, поскольку узлы с одинаковыми первыми компонентами не соединяются ребрами. Так как в этой клике в точности q узлов, то узлы клики взаимно однозначно соответствуют сомножителям формулы F. Пусть узлы клики имеют вид И, т], l<i<(7. Пусть Si={«/jfim.=«/,

где 1<1<9 и «/ - переменная} и 82={у\хш.=У, где и «/ -

переменная}. Иными словами. Si и Sg - множества переменных и отрицаний переменных соответственно, представленных узлами клики. Тогда SinSg=0, ибо в противном случае какие-то узлы Is, mg] и [t, mj], для которых Xsm=Xtmf, соединялись бы ребром. Если положить переменные из Si равными 1, а из Sg равными О, то каждая формула Fi примет значение 1. Поэтому формула F выполнима. □

Пример 10.5. Рассмотрим формулу Е=(у1+уг)(у2+Уз) {Уз+yi). Литералы таковы:

Хц - Уи Х2х = У2) Х1 = у,

Xi2-yit Х22=Уз, Х2~У\-

Конструкция из теоремы 10.5 дает граф, изображенный на рис. 10.7.

Например, узел [1, 1] не соединен с [1, 2], потому что первые

компоненты одинаковы, и с [3, 2], потому что Jfu=«/i и Хз2=Уи

а с остальными тремя узлами соединен.

В формуле F три сомножителя, и оказывается, что в графе на )ис. 10.7 две 3-клики, а именно {[1,1], [2,1], [3,1]} и {[1,2], [2,2], 3,2]}. В первой клике представлены три литерала у у2 и уз.





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