Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 252
Текст из файла (страница 252)
(1 Ч 1)) Л 1 = (1 Ч О) Л 1 (34.2) Теорема 34. 9 Задача о выполнимости булевых формул является ХР-полной. Докоэо4иельсилво. Сначала докажем, что ЯАТ Е ХР. Затем покажем, что язык БАТ ХР-сложный, для чего продемонстрируем справедливость соотношения С1ВСШТ-ЯАТ <р ЯАТ. Согласно лемме 34.8 этого достаточно для доказательства теоремы. Чтобы показать, что язык ЯАТ относится к классу МР, покажем, что сертификат, состоящий из выполняющего набора входной формулы ф, можно верифицировать за полиномиальное время. В алгоритме верификации каждая содержащаяся в формуле переменная просто заменяется соответствующим значением, после чего вычисляется выражение, как это было проделано выше с уравнением (34.2).
Эту задачу легко выполнить за полиномиапьное время. Если в результате получится значение 1, то формула выполнима. Таким образом, первое условие леммы 34,8 выполняется. Чтобы доказать, что язык ЯАТ МР-сложный, покажем, что С1ВС1)1Т-ЯАТ «р ЯАТ. Другими словами, покажем„как любой экземпляр задачи о выполнимости схемы можно за полиномиальное время привести к экземпляру задачи о выполнимости формулы. С помощью индукции любую логическую комбинационную так что данная формула ф принадлежит языку ЯАТ, Простейший прямолинейный алгоритм, позволяющий определить, выполнима ли произвольная булева формула, не укладывается в полиномиально-временные рамки.
В формуле ф с и переменными всего имеется 2" возможных вариантов присваивания. Если длина (ф) выражается полиномиальной функцией от и, то для проверки каждого варианта присваивания потребуется время П(2"), т.е. оно выражается функцией, показатель роста которой превосходит полиномиальную функцию от длины (ф). Как видно из приведенной ниже теоремы, сугцествование алгоритма с полиномиальным временем маловероятно. ИЗ6 Часть Пь Избранные темы Рис.
34ДВ. Приведение задачи о выполнимости схем к задаче о выполнимости формул; формула, полученная в результате выполнения ааторнтма приведения, сспержит переменные, соответстауюпме квкдому проводу схемы. (х4 чч хэ) (Хь 44 (Хт ч Х2)) (Х6 44 Х4) (хт ет (хз Л хз Л х4)) (Ха тч (Х6 ч Х6)) (Х9 чт (Хб ч Х7)) (хю чч (х7 Л хВ Л х9)) . ф = хю Л схему можно выразить в виде булевой формулы. Для этого достаточно рассмотреть элемент, который выдает выходное значение схемы, и по индукции выразить каждое входное значение этого элемента в виде формул.
Формула схемы получается путем выписывания выражения, в котором функция элемента применяется к формулам входов. К сожалению, такой незамысловатый метод не может стать основой приведения за полиномиальное время. Как предлагается показать в упр. 34.4.1, общие вспомогательные формулы, соответствующие элементам, коэффициент ветвления которых равен 2 илн превышает зто значение, могут привести к экспоненциальному росту размера формулы. Таким образом, алгоритм приведения должен быть несколько остроумнее.
Основная идея приведения задачи С1ВСШТ-ЯАТ к задаче ЯАТ для схемы из рис. 34.8, (а) проиллюстрирована на рис. 34.10. Каждому проводу х; схемы С сопоставляется одноименная переменная формулы 4. Тогда надлежащее действие элемента можно выразить в виде небольшой формулы, включающей в себя переменные, которые соответствуют проводам, подсоединенным к этому элементу.
Например, действие элемента И выражается формулой Хзо +4 (хтЛхвЛхв). Будем называть каждую такую небольшую формулу иодеыранееннем (с1апзе). Формула ф, которая является результатом выполнения алгоритма приведения, получается путем конъюнкции (элемент И) выходной переменной схемы с выражением, представляющим собой конъюнкцию взятых в скобки подвыражений, описывающих действие каждого элемента. Для схемы, изображенной на рисунке, формула имеет следующий вид: Глава 34. Г4Р-нолнота Для заданной схемы С легко получить такую формулу ф за полиномиальное время. Почему схема С выполнима именно тогда, когда выполнима формула ф? Если у схемы С имеется выполняющий набор, то по каждому проводу схемы передается вполне определенное значение, и на выходе схемы получается значение 1. Поэтому набор значений, передающихся по проводам схемы, в формуле ф приведет к тому, что значение каждого подвыражения в скобках в формуле ф будет равно 1, вследствие чего конъюнкция всех этих подвыражений будет равна 1.
Верно и обратное: если существует набор данных, для которого значение формулы ф равно 1, то схема С выполнима (это можно показать аналогично). Таким образом, показана справедливость соотношения С1КСШТ-ЯАТ <р ЯАТ, что и завершает доказательство теоремы. 3-С1ч Р-выполнимость ХР-полноту многих задач можно доказать путем приведения к ним задачи о выполнимости формул.
Однако алгоритм приведения должен работать с любыми входными формулами, что может привести к огромному количеству случаев, подлежащих рассмотрению. Поэтому часто желательно выполнять приведение с помощью упрощенной версии языка булевых формул, чтобы уменьшить количество рассматриваемых случаев (конечно же, ограничивать язык настолько, чтобы он стал распознаваемым за полиномиальное время, при этом нельзя). Одним из таких удобных языков является язык формул в 3-конъюнктивной нормальной форме З-СЫР-ЯАТ.
Определим задачу о 3-СИР выполнимости в описанных ниже терминах. Литерал (Рйега!) в булевой формуле — это входящая в нее переменная или отрицание этой переменной. Булева формула приведена к конвюнктивной нормальной форме (соп!ппс!1не поппа! Гопп — СХР), если она имеет вид конъюнкции (элемент И) выражений (с!апзез), каждое из которых представляет собой дизъюнкцию (элемент ИЛИ) одного или нескольких литералов. Булева формула выражена в 3- коньюнктивнои нормальной форме (3-соп!цпс!(ае попив! !опп), или З-СЮР, если в каждом подвыражении в скобках содержится ровно три различных литерала.
Например, булева формула (Х1М Х1 и ХЗ)Л(ХЗЧХ2~IХ4)А( Х1 и ХЗЧ Х4) принадлежит классу 3-СХР. Первое из трех подвыражений в скобках имеет вид (х1 ~l -.х1 м - хз) и содержит три литерала — хп х4 и хз. В задаче 3-С1н'г-ЯАТ спрашивается, выполнима лн заданная формула ф, принадлежащая классу 3-СХгВ В приведенной ниже теореме показано, что алгоритма с полиномиальным временем работы, способного определять выполнимость даже таких простых булевых формул, скорее всего, не существует. теорема 34.10 Задача о выполнимости булевых формул в 3-конъюнкгивной нормальной форме является ХР-полной. луг Часть УГ1. Избраннме тенм Уз 1 л',. кз.% лз ,Р-.', хз зз хз Рис.
34Л1. Дерево, соответствунллее формуле ф = ((хз -ь хз)ч (( хз ьь хз)ч хь)) л вз. ф = ((хз — + хг)Ч' ((. хз о+ ха) Чхз)) Л-хг . (34.3) Если входная формула содержит подвыражение, такое как дизьюнкция или коньюнкция нескольких литералов, то, воспользовавшись свойством ассоциативности, можно провести расстановку скобок в выражении таким образом, чтобы каждый внутренний узел полученного в результате дерева содержал 1 или 2 дочерних узла. Теперь такое бинарное синтаксическое дерево можно рассматривать как схему, предназначенную для вычисления функции. Имитируя приведение из доказательства теоремы 34.9, введем переменные рл для выхода из каждого внутреннего узла.
Затем перепишем исходную формулу ф как конъюнкцию переменной, соответствующей корню дерева, и выражений, описывающих операции в каждом узле. Для формулы (34.3) полученное в результате Доказазлельслзвзх Рассуждения, которые использовались в теореме 34.9 для доказательства того, что БАТ Е МР, применимы и для доказательства того, что 8-СИР-ЯАТ б ХР. Таким образом, согласно лемме 34.8 нам требуется лишь показать, что БАТ <р З-СИР-БАТ.
Алгоритм приведения можно разбить на три основных этапа. На каждом этапе входная формула ф последовательно приводится к 3-конъюнктивной нормальной форме. Первый этап аналогичен тому, который был использован при доказательстве С1КС1ЛТ-БАТ <р ЯАТ в теореме 34.9. Сначала для входной формулы сз конструируется бинарное "синтаксическое" дерево, листья которого соответствуют литералам, а узлы — соединительным элементам. На рис. 34.11 показано такое синтаксическое дерево для формулы Глава 34. З/Р-па4нота ~ЗЗ выражение имеет следующий вид: Ф = у4 Л (у4 <-> (уз Л хз)) Л (Уз ~+ (Уз / У4)) Л (УЗ <-> (Х4 -Г ХЗ)) /'(У4 +4 Уб) Л (Уб 44 (Уб ~/ х4)) Л (Уб 44 ( х4 4+ хз)) . Обратите внимание, что полученная таким образом формула ф' представляет собой конъюнкцию выражений ф',, каждое из которых содержит не более трех литералов.
Единственное требование, которое может оказаться нарушенным, состоит в том, что каждое выражение в скобках должно быть дизьюнкцией трех литералов. На втором этапе приведения каждое подвыражение в скюбках ф'; преобразуется в конъюнктивную нормальную форму. Составим таблицу истинности формулы ф', путем ее вычисления при всех возможных наборах значений ее переменных. Каждая строка такой таблицы соответствует одному из вариантов набора переменных выражения и содержит сам вариант и результат вычисления исследуемого подвыражения. С помощью элементов таблицы истинности, которые приводят к нулевому результату в формуле, можно записать формулу, эквивапентную подвыражению - ф',, в дизъюнктивной нормальной форме (сйб)юпсбте попив! Ропп— РХР), которая представляет собой дизъюнкцию конъюнкций.
Затем эта формула с помощью законов де Моргана (аЛЬ) = а / Ь, - (а~/Ь) = аЛ- Ь преобразуется в СХР-формулу ф," путем замены всех литералов их дополнениями и замены операций дизъюнкций и конъюнкций одна другой. В качестве примера преобразуем выражение ф', = (У4 4+ (уз л хз)) в СХР. Таблица истинности для этой формулы представлена на рис. 34.12. ОХР-формула, эквивалентнаЯ выРажению — 4бю имеет виД (у4 ЛУЗ ЛХЗ) ~/(У4 Л УЗ Лха)Ч (у4 Л-ТУЗЛ хэ) Ч (-~уз ЛУЗ Л ХЗ) .
Обращая и применяя закюны де Моргана, получим СХР-формулу ф4 = ( у4 ~/ уз '/ - хз) Л (-'у4 Ч уз '/ хз) Л( У4 УУз Чхз) Л(У1 Ч УзЧхз), кюторая эквивалентна исходной формуле фю Теперь каждое подвыражение 4Ь',, содержащееся в формуле ф', преобразовано в СХР-формулу ф,", так что ф' эквивалентно СХР-формуле ф"„состоящей из конь- Честь 122 Избранные темы ИЗ4 Рис. 34Л2. Таблица истинности лля выражения (Ю <+ (уа зт ха)). юнкции выражений ф,". Кроме того, каждое подвыражение формулы фн содержит не более трех литералов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
