Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 233
Текст из файла (страница 233)
Верно и обратное— если существует набор данных, для которого значение формулы р равно 1, то схема С выполнима (это можно показать аналогично). Таким образом, показана справедливость соотношения С!ксшт БАт <р ЯАт, что завершает доказательство теоремы. И 3-СЫР выполнимость ИР-полноту многих задач можно доказать путем приведения к ним задачи о выполнимости формул. Однако алгоритм приведения должен работать с любыми входными формулами, что может привести к огромному количеству случаев, подлежащих рассмотрению.
Поэтому часто желательно выполнять приведение с помощью упрощенной версии языка булевых формул, чтобы уменьшить количество рассматриваемых случаев (конечно же, ограничивать язык настолько, чтобы он стал распознаваем в течение полиномиального времени, при этом нельзя). Одним из таких удобных языков оказывается язык формул в 3-конъюктивной нормальной форме 3-СИР БАт. Определим задачу о 3-САЯР выполнимости в описанных ниже терминах. Лиизерал (!Йега1) в булевой формуле — это входящая в нее переменная или отрицание этой переменной.
Булева формула приведена к коиъизнктивиой нормальной фор- Глава 34. ХР-полнота 1123 ме (Сощппсбке Хоппа! Ропп, СХР), если она имеет вид конъюнкции (вентиль И) выранеений в скобках (с!апзез), каждое из которых представляет собой дизъюнкцию (вентиль ИЛИ) одного или нескольких литералов. Булева формула выражена в 3-конъюнктивной нормальной форме (3-сощппсг!че поппа1 1опп), или З-СЮГ, если в каждых скобках содержится ровно три различных литерала. Например, булева формула (х1 ~l 1х1 Ч ~хз) Л (хз ~l хз ~I х4) Л ( ~х1 Ч 1хз ~l 1Х4) принадлежит классу 3-СХЕ Первое из трех выражений в скобках имеет вид (х1 Ч вЂ” х1 Ч вЂ” хз) и содержит три литерала: хп хп-хз. В задаче 3-СХР Яхт спрашивается, выполнима ли заданная формула ф, принадлежащая классу 3-СХР. В приведенной ниже теореме показано, что алгоритм с полиномиальным временем работы, способный определять выполнимость даже таких простых булевых формул, скорее всего, не существует.
Теорема 34.10. Задача о выполнимости булевых формул в 3-конъюнктивной нор- мальной форме является ХР-полной. Доказательство. Рассуждения, которые использовались в теореме 34.9 для доказательства того, что Ялт Е ХР, применимы и для доказательства того, что 3-СХР Блт Е ХР. Таким образом, согласно лемме 34.8, нам требуется лишь показать, что Блт (р 3-СХР Блт. Алгоритм приведения можно разбить на три основных этапа. На каждом этапе входная формула ф последовательно приводится к 3-конъюнктивной нормальной форме. Первый этап аналогичен тому, который был использован при доказательстве соотношения Ялт <р 3-СХР Блт в теореме 34.9.
Сначала для входной формулы ф конструируется бинарное "синтаксическое" дерево, листья которого соответствуют литералам, а узлы — соединительным элементам. На рис. 34.11 показано такое синтаксическое дерево для формулы (34.3) ф = ((хз -+ хз) ~/ ' (( ~х1 ++ хз) Ч х4)) Л ~хз. Если входная формула содержит выражение в скобках„представляющее собой дизъюнкцию или конъюнкцию нескольких литералов, то, воспользовавшись свойством ассоциативности, можно провести расстановку скобок в выражении таким образом, чтобы каждый внутренний узел полученного в результате дерева содержал 1 или 2 дочерних узла. Теперь такое бинарное синтаксическое дерево можно рассматривать как схему, предназначенную для вычисления функции.
По аналогии с процедурой приведения в теореме 34.9, введем переменную уп соответствующую выходному значению каждого внутреннего узла. Затем перепишем исходную формулу ф как конъюнкцию переменной, соответствующей корню Часть Ч!!. Избранные темы 1124 Рис. 34.11. Дерево, соответствующее формуле ф= ((х1 +хг) У (( х1 <+ хз) Ух4))Л хз дерева, и выражений, описывающих операции в каждом узле. Для формулы (34.3) получившееся в результате выражение имеет следующий вид: ф' = У1 Л (У1 ~-+ (уз Л -х,)) Л Л (Уз + (Уз У У4)) Л Л (уз (х1 — хз)) Л Л (у4 <"+ уб) Л Л (уб ~ ~ (уб '4 х4)) Л Л (Уб + + ( 'Х1 +-+ хз)) .
Заметим, что полученная таким образом формула ф' представляет собой коньюнкцию выражений в скобках ф',, каждое из которых содержит не более трех литералов. Единственное дополнительное требование состоит в том, что каждое выражение в скобках должно быть логической суммой литералов.
На втором этапе приведения каждое выражение в скобках ф', преобразуется к конъюнктивной нормальной форме. Составим таблицу истинности формулы ф', путем ее вычисления при всех возможных наборах значений ее переменных. Каждая строка такой таблицы соответствует одному из вариантов набора, и содержит сам вариант и результат вычисления исследуемого выражения. С помощью элементов таблицы истинности, которые приводят к нулевому результату в формуле, можно составить формулу, эквивалентную выражению — ф';, в дизъюнктиеной нормальной форме (!31з)ппсцче Хоппе! Ропп, 0ХР), которая является дизъюнкцией конъюнкций. Затем эта формула с помощью законов де Моргана (1)еМогяав) Глава 34. ХР-полнота 1125 (уравнение (Б.2)) преобразуется в СХР-формулу 4>1 путем замены всех литералов их дополнениями и замены операций дизъюнкций и конъюнкций друг на друга.
В качестве примера преобразуем выражение 4~ —— (уз + (уз Л ~хз)) в СХР. Таблица истинности для этой формулы представлена в табл. 34.1. ПХР-формула, эквивалентная выражению — ф', имеет вид (уз л уз л хз) ч (уз л уз л хз) ч (у~ л уз л . хз) ч (- уз л уз л . хз). Применяя законы де Моргана„получим СХР-формулу ф~ = ( 'у1 Ч уз Ч - хз) Л (-'уз Ч уз Ч вЂ” хг) Л ( 'уз Ч уз Ч хз) Л (у~ Ч вЂ” уз Ч хз), которая эквивалентна исходной формуле ф',.
Таблица 34.1. Таблица истинности для выражения (у~ ~ (уя Л хз)) После того как каждое подвыражение ф',, содержащееся в формуле ф', оказывается преобразовано в СХР-формулу ф,", так что ф эквивалентно СХР-формуле ф", состоящей из конъюнкции выражений ф'. Кроме того, каждое подвыражение формулы фл содержит не более трех литералов. На третьем и последнем этапе приведения формула преобразуется таким образом, чтобы в каждых скобках содержалось точно 3 различных литерала.
Полученная в результате 3-СХР формула ф'л составлена из подвыражений, входящих в СХР-формулу ф". В ней также используются две вспомогательные переменные, которые будут обозначаться как р и д. Для каждого подвыражения С; из формулы 4)" в формулу ф"' включаются следующие подвыражения. ° Если С; содержит 3 различных литерала, то это подвыражение включается в формулу ф"' в неизменном виде. ° Если выражение С; содержит 2 различных литерала, т.е. если С; = (1~ Ч 1з), где 1з и 1з — литералы, то в качестве подвыражения в формулу ф"' включается выражение (1~ Ч 1з Ч р) Л (1~ Ч 1я Ч. р).
Литералы р и -р служат лишь Часть ЧП. Избранные темы 1126 для того, чтобы удовлетворялось требование о наличии в каждом подвыражении в скобках ровно трех разных литералов: выражение (11 Ч 1з Ч р) Л (11 Ч 1з Ч р) эквивалентно выражению (11 Ч 1з) и при р = О, и при р = 1. ° Если выражение С; содержит ровно 1 литерал 1, то вместо него в качестве подвыражения в формулу ф"' включается выражение (1 Ч р Ч д) Л (1ЧрЧ-9) Л (1 Ч рЧд) Л (1Ч- рЧ- д).
При любых значениях переменных р и д приведенная конъюнкция четырех подвыражений в скобках эквивалентна 1. Проверив каждый из описанных выше трех этапов, можно убедиться, что 3-СХР формула ф"' выполнима тогда и только тогда, когда выполнима формула ф. Как и в случае приведения задачи Сшсшт Блт к задаче Ялт, составление на первом этапе формулы ф' по формуле я) не повлияет на выполнимость. На втором этапе конструируется СХР-формула ф", алгебраически эквивалентная формуле ф'.
На третьем этапе конструируется 3-СХГ формула ф"'; результат которой эквивалентен формуле ф", поскольку присваивание любых значений переменным р и д приводит к формуле, алгебраически эквивалентной формуле ф". Необходимо также показать, что приведение можно выполнить в течение полиномиального времени. В ходе конструирования формулы ф'по формуле ф приходится добавлять не более одной переменной и одной пары скобок на каждый соединительный элемент формулы ф.
В процессе построения формулы фл по формуле 4' в формулу фл добавится не более восьми подвыражений в скобках на каждое подвыражение в скобках из формулы 4', поскольку каждое подвыражение в этой формуле содержит не более трех переменных и таблица его истинности состоит не более чем из 2з = 8 строк. В ходе конструирования формулы ф"' по формуле ф" в формулу фл' добавляется не более четырех подвыражений на каждое подвыражение формулы ф".
Таким образом, размер полученной в результате формулы фл' выражается полиномиальной функцией от длины исходной формулы. Следовательно, каждый этап можно легко выполнить в течение полиномиального времени. й Упражнения 34.4-1. Рассмотрите приведение "в лоб" (время работы которого не выражается полиномиальной функцией) из теоремы 34.9. Опишите схему размера а, размер которой после преобразования этим методом превратится в формулу размер которой выражается показательной функцией от и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
