Алгоритмы - построение и анализ (1021735), страница 232
Текст из файла (страница 232)
Именно для этой задачи впервые была доказана Хр-полнота. Сформулируем задачу о выполнимости формулы ((опии!а запзбаЬ!!йу) в терминах языка БАт. Экземпляр языка БАт — это булеза формула ф, состоящая из перечисленных ниже элементов. 1. п булевых переменных: хм ха,...,х„. 2. т булевых соединяющих элементов, в роли которых выступает произвольная логическая функция с одним или двумя входными значениями и одним выходным значением, например, д (И), Ч (ИЛИ), (НЕ), -~ (импликация), ~-> (эквивалентность). Часть Ч11. Избранные темы 1120 3. Скобки.
(Без потери общности предполагается, что лишние скобки не употребляются, т.е. что на каждый логический соединяющий элемент приходится не более одной пары скобок.) Логическую формулу ф легко закодировать строкой, длина которой выражается полиномиальной функцией от и+т. Как и для логических комбинационных схем, паборан значений (Птк1з азз18птеп1) логической формулы ф называется множество значений переменных этой формулы, а выполняющим набором (за11зГушй азз18пшеп1) — такой набор значений, при котором результат вычисления формулы равен 1. Формула, для которой существует выполняющий набор, является выполнимой (за11збаЫе). В задаче о выполнимости спрашивается, выполнима ли данная формула.
В терминах формальных языков эта задача имеет вид Ялт = ((ф): ф — выполнимая булеза формула) . В качестве примера приведем формулу ф = ((хз — + хз) ~/ ~ (( ~х1 <-+ хз) Ч хя)) Л ~х2, для которой существует выполняющий набор (хз = О, хз = О, хз = 1, х4 = 1), по- скольку ф= ИО 0) Ч (( 0 1) ~/1)) Л. 0 = = (1 ~/ - (1 Ч 1)) Л 1 = =(1ЧО)Л1= = 1. (34.2) Таким образом, формула ф принадлежит языку Блт. Прямолинейный алгоритм, позволяющий определить, выполнима ли произвольная булеза формула, не укладывается в полиномиально-временные рамки. В формуле ф с п переменными всего имеется 2" возможных вариантов присваивания. Если длина (ф) выражается полиномиальной функцией от п, то для проверки каждого варианта присваивания потребуется время й(2"), т.е.
оно выражается функцией, показатель роста которой превосходит полиномиальную функцию от длины (ф). Как видно из приведенной ниже теоремы, существование алгоритма с полиномиальным временем маловероятно. Теорема 34.9. Задача о выполнимости булевых формул является ХР-полной. Доказательство. Сначала докажем, что Блт е ХР. Затем покажем, что язык Блт Хр-сложный, для чего продемонстрируем справедливость соотношения Сшсшт ЗАт (<р Блт.
Согласно лемме 34.8, этого достаточно для доказательства теоремы. Чтобы показать, что язык Ялт относится к классу 1ЧР, покажем, что сертификат, состоящий из выполняющего набора входной формулы ф, можно верифицировать Глава 34. МР-полнота 1121 в течение полиномиального времени. В алгоритме верификации каждая содержащаяся в формуле переменная просто заменяется соответствующим значением, после чего вычисляется выражение, как это было проделано с уравнением (34.2). Эту задачу легко выполнить в течение полиномиального времени.
Если в результате получится значение 1, то формула выполнима. Таким образом, первое условие леммы 34.8 выполняется. Чтобы доказать, что язык Блт Хр-сложный, покажем, что справедливо соотношение С1ксшт Блт <р Блт. Другими словами, любой экземпляр задачи о выполнимости схемы можно в течение полиномиального времени свести к экземпляру задачи о выполнимости формулы. С помощью индукции любую логическую комбинационную схему можно выразить в виде булевой формулы.
Для этого достаточно рассмотреть вентиль, который выдает выходное значение схемы, и по индукции выразить каждое входное значение этого вентиля в виде формул. Формула схемы получается путем выписывания выражения, в котором функции вентиля применяются к формулам входов. К сожалению, такой незамысловатый метод не может стать основой приведения в течение полиномиального времени. Как предлагается показать в упражнении 34.4-1, общие вспомогательные формулы, соответствующие вентилям, коэффициент ветвления которых равен 2 или превышает это значение, могут привести к экспоненциальному росту размера формулы. Таким образом, алгоритм приведения должен быть несколыю остроумнее. Основная идея приведения задачи С1кс~лт БАт к задаче Блт для схемы из рис.
34.8а проиллюстрирована на рис. 34.10. Каждому проводу хз схемы С сопоставляется одноименная переменная формулы ф. Тогда надлежащее действие вентиля можно выразить в виде формулы, включающей в себя переменные, которые соответствуют проводам, подсоединенным к этому вентилю. Например, действие вентиля И выражается формулой хго (хт Л ха Л хо). Формула ф, которая является результатом выполнения алгоритма приведения, получается путем конъюнкции (вентиль И) выходной переменной схемы с выражением, представляющим собой конъюнкцию взятых в скобки выражений, описывающих действие каждого вентиля.
Для схемы, изображенной на рисунке, формула имеет такой вид: ф = хю Л (х4 «-+ -«хз) Л Л (хь +.+ (х1 ~/ хз)) Л Л (хо «+ ' х4) Л Л (хт + > (х1 Л хз Л х4)) Л Л (х, «-+ (х, Ч хо)) Л Л (хв (хо Ч х,)) Л Л (х|о + (хт Лхв Лхо)). Часть Ч!1. Избранные темы 1122 Рис. 34.10. Приведение задачи о выполнимости схем к задаче о выполнимости формул; формула, полученная в результате выполнения алгоритма приведения, содержит переменные, соответствующие каждому проводу схемы Для заданной схемы С легко получить такую формулу ф в течение полиномиального времени.
Почему схема С выполнима именно тогда, когда выполнима формула ф? Если у схемы С имеется выполняющий набор, то по каждому проводу схемы передается вполне определенное значение, и на выходе схемы получается значение 1. Поэтому набор значений, передающихся по проводам схемы, в формуле ф приведет к тому, что значение каждого выражения в скобках в формуле ф будет равно 1, вследствие чего конъюнкция всех этих выражений равна 1. Верно и обратное— если существует набор данных, для которого значение формулы р равно 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 +-+ хз)) .
Заметим, что полученная таким образом формула ф' представляет собой коньюнкцию выражений в скобках ф',, каждое из которых содержит не более трех литералов. Единственное дополнительное требование состоит в том, что каждое выражение в скобках должно быть логической суммой литералов. На втором этапе приведения каждое выражение в скобках ф', преобразуется к конъюнктивной нормальной форме. Составим таблицу истинности формулы ф', путем ее вычисления при всех возможных наборах значений ее переменных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
