набор. Подавая на вход схемы С значения переменных из этого набора, мы получим определенные значения на каждом проводе схемы. При этом выходным значением схемы будет 1. Эти значения и будут выполняющим набором для формулы Lp.

Напротив, если мы имеем некоторый выполняющий набор для формулы Lp, то он задаёт некоторое согласованное распределение значений по проводам схемы, при котором выходное значение равно 1, и потому схема выполнима.

Таким образом, CIRCUIT-SAT р SAT, что и требовалось доказать.

Выполнимость 3-CNF формул

Для многих задач удаётся доказать их NP-полноту, сведя к ним задачу о выполнимости формул. При этом удобно ограничить класс формул, выполнимость которых нас интересует - чем этот класс меньше, тем легче осуществить сведение. (При этом, конечно, задача о выполнимости формул из этого класса должна оставаться NP-полной.) На практике оказывается удобным класс формул в 3-конъюнктивной нормальной форме (3-conjunctive normal form), сокращённо обозначаемый 3-CNF. Такие формулы представляют собой конъюнкцию нескольких подформул, каждая из которых есть дизъюнкция ровно трёх различных литералов (литерал - это переменная или отрицание переменной).

Например, формула

(х\ V -1Жх V ж2) Л (ж3 V ж2 V ж4) Л (-1Ж1 V -1Ж3 V -*х±)

принадлежит классу 3-CNF. Первая из трёх ее дизъюнкций есть (х\ V -1Ж1 V ж2); она содержит литералы х\, -*х\ и -1Ж2.

Задача о выполнимости формул из класса 3-CNF, обозначаемая 3-CNF-SAT, является NP-полной со всеми вытекающими последствиями (вряд ли для неё есть полиномиальный алгоритм; её можно использовать для доказательства NP-полноты других задач).

Теорема 36.10

Задача проверки выполнимости формулы из класса 3-CNF NP-полна.

Доказательство

Язык 3-CNF-SAT принадлежит классу NP по тем же причинам, что и язык SAT (теорема 36.9). Чтобы доказать, что задача 3-CNF-SAT является NP-трудной, мы покажем, что SAT р 3-CNF-SAT, и останется сослаться на лемму 36.8.

Сведение будет использовать ту же идею, что и доказательство теоремы 36.9 (на самом деле можно было бы модифицировать это доказательство так, чтобы получалась формула из класса 3-CNF).

Пусть дана произвольная формула Lp. Построим «дерево разбора» этой формулы; листья этого дерева соответствуют литералам, а внутренние вершины - пропозициональным связкам. На рис. 36.9

показано такое дерево для формулы

ср = ((si -> ж2) V -((-1ж1 f-> ж3) V ж4)) Л -1Ж2.(36.3)

Мы считаем, что в формуле не встречаются дизъюнкции или конъюнкции более чем двух подформул (это ограничение не имеет значения, так как всегда можно расставить недостающие скобки). Таким образом, каждая внутренняя вершина имеет одного или двух потомков. Полученное дерево разбора можно рассматривать как схему, вычисляющую булеву функцию (соответствующую формуле).

Далее действуем как в теореме 36.9. Введем переменные уг- для каждой внутренней вершины построенной схемы. Теперь можно вместо исходной формулы написать конъюнкцию переменной, соответствующей корню дерева разбора, и подформул, утверждающих корректность операций в каждой вершине. Например, для формулы (36.3) получится формула

Ч> = у1ну1 & (у2 Л -№)) Л(у2 (у3 Vy4)) Л(у3 (a;i -> х2)) Л(у4 & (-.у5))

Л(у5 (ye Vi4)) Л(у6 (->a;i ж3)).

Полученная формула ср является конъюнкцией нескольких подформул, каждая из которых содержит не более 3 переменных - но эти подформулы ещё не являются дизъюнкциями трёх различных литералов.

Что ж, остаётся заменить каждую из этих подформул на конъюнкцию нескольких литералов. Это делается так: составим таблицу значений для этой подформулы (как на рис. 36.10) и посмотрим на строки, в которых подформула ложна (имеет значение 0). Для каждой из этих строк напишем дизъюнкцию трёх литералов, которая будет ложной как раз при этих значениях переменных, а затем напишем конъюнкцию этих дизъюнкций, которая будет эквивалентна рассмотренной подформуле от трёх переменных.

Для формулы из нашего примера таблица истинности показана на рис. 36.10, формула ложна в четырёх случаях, и записывая конъюнкции, исключающие каждый из этих четырёх случаев, получаем формулу

ьу1 V -ij/2 V ->ж2) Л (-.yi V у2 V -.ж2) Л (-.yi V у2 V ж2) Л (yt V ->у2 V ж2),

которая эквивалентна формуле (у\ <ФФ (у2 Л х2)).

Осталась ещё одна небольшая трудность - нам надо, чтобы каждая дизъюнкция содержала ровно три переменных. Для этого

можно добавить фиктивные переменные - или на этапе построения таблицы истинности, или сейчас: формулу pvg можно заменить на (р V q V г) Л (р V q V ->г), а формулу р можно заменить на

(р V q V г) Л (р V q V ~т) Л (р V -ig V г) Л (р V -ig V -т)Л

Легко видеть, что полученная в итоге формула выполнима в том и только том случае, когда выполнима исходная формула (на первом шаге это обосновывается как в теореме 36.9, а дальше мы заменяли формулы на эквивалентные). Ясно также, что длина новой формулы ограничена полиномом от длины старой и что все этапы нашего построения выполнимы за полиномиальное время.

Упражнения

36.4-1

Покажите, что обсуждаемый в начале доказательства теоремы 36.9 прямой метод сведения не годится, предъявив схему размера п, которая переводится в формулу экспоненциального (on п) размера.

36.4-2

Постройте формулу из класса 3-CNF, применив к формуле (36.3) алгоритм из доказательства теоремы 36.10. 36.4-3

Профессор утверждает, что он упростил доказательство теоремы 36.10 и придумал способ преобразовать произвольную формулу в логически эквивалентную ей формулу (с теми же переменными), принадлежащую классу 3-CNF. Почему он не прав?

36.4-4

Покажите, что задача определения, является ли данная пропозициональная формула тавтологией, NP-полна в классе со - NP. (Указание: см. упражнение 36.3-6.)

36.4-5

Покажите, что за полиномиальное время можно определить, является ли данная булева формула в «дизъюнктивной нормальной форме» (дизъюнкция подформул, каждая из которых является конъюнкцией литералов) выполнимой.

36.4-6

Пусть кто-то придумал полиномиальный алгоритм, проверяющий выполнимость любой пропозициональной формулы. Как можно использовать этот алгоритм для отыскания выполняющего набора (для данной выполнимой формулы) за полиномиальное время?

36.4-7

Рассмотрим язык 2-CNF-SAT, который состоит из выполнимых формул в конъюнктивной нормальной форме, в которых каждый конъюнктивный член является дизъюнкцией не более чем двух литералов. Докажите, что 2-CNF-SAT £ Р. Постройте как можно более быстрый разрешающий алгоритм. (Указание: Поскольку (ж У у) эквивалентно выражению (->ж -> у), можно свести 2-CNF-SAT к