Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 232
Текст из файла (страница 232)
Объясните, какая ошибка содержится в рассуждениях профессора. 34.4 Доказательство 1 1Р-полноты ХР-полнота для задачи о выполнимости схем основана на непосредственном доказательстве соотношения Е <р Сщсп1т БАт для каждого языка Ь б ХР. В этом разделе будет показано, как доказать ХР-полноту языка без непосредственного приведения каждого языка из класса ХР к заданному языку. Проиллюстрируем зту методику, доказав ХР-полноту различных задач на выполнимость формул. Намного большее количество примеров применения этой методики содержится в разделе 34.5.
Основой рассматриваемого в этом разделе метода, позволяющего доказать ХР- полноту задачи, служит сформулированная ниже лемма. Лемма 34.8. Если язык Ь такой, что Ь' <р Ь для некоторого языка Ь' Е ХРС, то язык Ь вЂ” ХР-сложный. Более того, если Ь Е ХР, то Б Е ХРС. Глава 34. МР-полнота 1119 Доказатеиьсиюво. Поскольку язык Ь' ХР-полный, для всех Ь" е ХР выполняется соотношение Ь" <р Б'. Согласно условию леммы Ь' <р Ь, поэтому в силу транзитивности (упражнение 34.3-2) мы имеем Ьа <р Ь, что и показывает, что язык Ь вЂ” ХР-сложный. Если Ь б ХР, то мы также имеем Ь Е ХРС. И Другими словами, если язык Б', о котором известно, что он — Хр-полный, удается свести к языку Ь, тем самым к этому языку неявно сводится любой язык класса ХР.
Таким образом, лемма 34.8 позволяет сформулировать метод доказательства ХР-полноты языка Ь, состоящий из перечисленных ниже этапов. 1. Доказывается, что Ь е ХР. 2. Выбирается язык Ь', для юторого известно, что он — ХР-полный. 3. Описывается алгоритм, который вычисляет функцию Г, отображающую каждый экземпляр х Е (О, 1)' языка Ь' на экземпляр г" (х) языка Ь.
4. Доказывается, что для функции г" соотношение х Е Е/ выполняется тогда и только тогда, когда Г' (х) Е Ь для всех х Е (О, Ц'. 5. Доказывается, что время работы алгоритма, вычисляющего функцию У, выражается полиномиальной функцией. (Выполнение этапов 2-5 доказывает, что язык Ь ХР-сложный.) Такая методология приведения с помощью одного языка, для которого известно, что он ХР-полный, намного проще, чем процесс, когда непосредственно демонстрируется, как выполнить приведение каждого языка из класса ХР.
Доказательство соотношения С1ксг!1т БАт б ХРС вЂ” первый важный шаг в этом направлении. Знание того факта, что задача о выполнимости схемы является ХР-полной, позволяет доказывать ХР-полноту других задач намного проще. Более того, по мере расширения списка известных ХР-полных задач у нас появляется все больше возможностей для выбора языков, юторые будут использоваться для приведения. Выполнимость формулы Чтобы проиллюстрироватьметодику приведения, докажемХР-полноту задачи, состоящей в определении того, выполнима ли не схема, а формула. Именно для этой задачи впервые была доказана Хр-полнота.
Сформулируем задачу о выполнимости формулы ((опии!а запзбаЬ!!йу) в терминах языка БАт. Экземпляр языка БАт — это булеза формула ф, состоящая из перечисленных ниже элементов. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
