dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 98
Текст из файла (страница 98)
Класс NP также замкнут относительно каждой из операций, перечисленных вупражнении 10.1.6, за (предполагаемым) исключением операции дополнения(пункт е). Замкнут ли класс NP относительно дополнения — неизвестно; этотвопрос обсуждается в разделе 11.1. Докажите, что NP замкнут относительноопераций из пунктов а–д упражнения 10.1.6.10.2. Ïåðâàÿ NP-ïîëíàÿ ïðîáëåìàТеперь познакомимся с первой NP-полной проблемой — проблемой выполнимостибулевых формул. Ее NP-полнота доказывается путем непосредственного сведения к нейязыка любой недетерминированной МТ с полиномиальным временем.10.2.1. Ïðîáëåìà âûïîëíèìîñòèБулевы формулы (выражения) строятся из следующих элементов.1.Булевы переменные, принимающие значения 1 (истина) или 0 (ложь).2.Бинарные операторы ∧ и ∨, обозначающие логические связки И и ИЛИ двух формул.3.Унарный оператор ¬, который обозначает логическое отрицание.4.Скобки для группирования операторов и операндов, если необходимо изменить порядок старшинства (приоритетов) операторов, принятый по умолчанию (вначалеприменяется ¬, затем ∧ и, наконец, ∨).Пример 10.6.
Примером булевой формулы является x ∧ ¬(y ∨ z). Подформула y ∨ zимеет значение “истина”, если истинна хотя бы одна из переменных y или z, и “ложь”, если436Стр. 436ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛобе они ложны. Большая подформула ¬(y ∨ z) истинна лишь тогда, когда y ∨ z ложно, т.е.когда обе переменные ложны.
Если хотя бы одна из y или z истинна, то ¬(y ∨ z) ложно.Рассмотрим, наконец, всю формулу. Поскольку она представляет собой логическое Идвух подформул, то она истинна только тогда, когда истинны обе подформулы, т.е.x∧¬(y ∨ z) истинна тогда и только тогда, когда x истинна, а y и z ложны. Выбрать подстановку (набор значений переменных) для данной булевой формулыE — значит приписать значение “истина” или “ложь” каждой из переменных, фигурирующих в E. Значение формулы E при данной подстановке T, обозначаемое как E(T), —это результат вычисления E, в которой каждая из ее переменных x заменена значениемT(x) (“истина” или “ложь”), которое соответствует x в T.Формула E истинна при подстановке T, или подстановка T удовлетворяет формулеE, если E(T) = 1, т.е.
данная подстановка T делает формулу E истинной. Булева формула E называется выполнимой, если существует хотя бы одна подстановка T, для которой E истинна.Пример 10.7. Формула x∧¬(y ∨ z) из примера 10.6 выполнима. Мы убедились, что этаформула истинна при подстановке T, определенной равенствами T(x) = 1, T(y) = 0 иT(z) = 0, поскольку принимает значение 1.
Мы также заметили, что T — единственнаяподстановка, удовлетворяющая этой формуле, поскольку для остальных семи комбинаций значений трех переменных формула ложна (принимает значение 0).В качестве еще одного примера рассмотрим формулу E = x ∧ (¬x ∨ y) ∧ ¬y. Утверждаем, что E невыполнима. Поскольку переменных в ней всего две, то число возможныхподстановок есть 22 = 4, так что нетрудно проверить их и убедиться, что при всех формула E принимает значение 0. Однако это можно обосновать и по-другому. E истиннатолько тогда, когда все три члена, связанных ∧, истинны. Это значит, что x должно бытьистинным (из-за первого члена), а y — ложным (из-за третьего члена). Но для такой подстановки значение среднего члена ¬x ∨ y ложно. Таким образом, значение E не можетбыть истинным, и E действительно невыполнима.В одном из рассмотренных примеров у формулы была лишь одна удовлетворяющаяподстановка, а в другом их вообще не было.
Существует также множество примеров, вкоторых у формулы есть более одной удовлетворяющей подстановки. Например, рассмотрим F = x ∨ ¬y. Значение F есть 1 для трех следующих подстановок.1.T1(x) = 1; T1(y) = 1.2.T2(x) = 1; T2(y) = 0.3.T3(x) = 0; T3(y) = 0.F принимает значение 0 лишь для четвертой подстановки, где x = 0 и y = 1. Таким образом, F выполнима. Проблема выполнимости состоит в следующем.• Выяснить, выполнима ли данная булева формула.10.2. ÏÅÐÂÀß NP-ÏÎËÍÀß ÏÐÎÁËÅÌÀСтр. 437437Проблема выполнимости обычно обозначается как ВЫП.
Если рассматривать ее какязык, то проблема ВЫП есть множество (закодированных) выполнимых булевых формул. Цепочки, которые либо не образуют правильные коды булевых формул, либо являются кодами невыполнимых булевых формул, не принадлежат ВЫП.10.2.2. Ïðåäñòàâëåíèå ýêçåìïëÿðîâ ÂÛÏСимволами в булевых формулах являются ∧, ∨, ¬, левые и правые скобки, а такжесимволы, представляющие переменные. Выполнимость формулы зависит не от именпеременных, а от того, являются ли два вхождения переменных одной и той же переменной или двумя разными.
Таким образом, можно считать, что переменными являются x1, x2, …, хотя в примерах в качестве имен переменных по-прежнему используетсяне только x, но и имена вроде y или z. Считается также, что переменные переименованытак, что используются наименьшие из возможных индексов. Например, переменная x5 неиспользуется, если в той же формуле не использованы переменные x1–x4.Поскольку число переменных, встречающихся в булевых формулах, может быть бесконечным, то мы сталкиваемся с уже знакомой проблемой разработки кода, имеющегофиксированный конечный алфавит, для представления формул с произвольным, скольугодно большим, числом переменных. Только имея такой код, можно говорить о ВЫПкак о “проблеме”, т.е. языке с фиксированным алфавитом, состоящем из кодов выполнимых булевых формул.
Будем использовать следующий код.1.Символы ∧, ∨, ¬, ( и ) представляют самих себя.2.Переменная xi представляется символом x с дописанной к нему последовательностью нулей и единиц — двоичной записью числа i.Таким образом, алфавит проблемы/языка ВЫП содержит всего восемь символов. Все экземпляры ВЫП являются цепочками символов в этом фиксированном конечном алфавите.Пример 10.8. Рассмотрим формулу x ∧ ¬(y ∨ z) из примера 10.6. Первое, что нужносделать для ее кодирования, — заменить переменные индексированными символами x.Поскольку переменных три, следует использовать x1, x2 и x3. Выбор xi для замены переменных x, y и z зависит от нас.
Положим для определенности x = x1, y = x2 и z = x3. Тогдаформула принимает вид x1 ∧ ¬(x2 ∨ x3), и ее кодом является x1 ∧ ¬(x10 ∨ x11). Отметим, что длина закодированной булевой формулы примерно равна числу позиций в этой формуле, если считать каждое вхождение переменной за 1. Разница возникаетиз-за того, что если формула имеет m позиций, то она может содержать O(m) переменных, и для кодирования каждой из них может понадобиться O(log m) символов. Такимобразом, формула длиной m позиций может иметь код длиной n = O(m log m) символов.Однако разница между m и m log m, очевидно, ограничена полиномом.
Поэтому, если нас интересует лишь, можно ли решить проблему за время, полиномиально зависящее от размера входных данных, то длину кода формулы и число позиций в ней различать не обязательно.438Стр. 438ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛ10.2.3. NP-ïîëíîòà ïðîáëåìû ÂÛÏДокажем “теорему Кука”, утверждающую, что ВЫП NP-полна. Для доказательства,что некоторая проблема является NP-полной, сначала нужно показать, что она принадлежит классу NP, а затем — что к ней сводится любой язык из NP.
Как правило, для доказательства второй части к нашей проблеме полиномиально сводится какая-либо другаяNP-полная проблема, а затем применяется теорема 10.5. Но пока у нас нет ни одной NPполной проблемы, которую можно было бы свести к ВЫП. Поэтому нам остается толькосводить каждую без исключения проблему из NP к ВЫП.Теорема 10.9 (теорема Кука). Проблема ВЫП NP-полна.Доказательство. В первой части доказывается, что ВЫП принадлежит NP. Сделатьэто довольно легко.1.С помощью свойства недетерминированности НМТ для данной формулы E угадываем подстановку T. Если код E имеет длину n, то многоленточной НМТ для этогодостаточно времени O(n).
Заметим, что у НМТ есть много возможностей выбора переходов, и по окончании процесса угадывания она может иметь 2n различных МО,где каждая ветка представляет угадывание отдельной подстановки.2.Находим значение E для подстановки T. Если E(T) = 1, то допускаем. Отметим, чтоэта часть детерминирована. Тот факт, что другие ветки могут не приводить к допусканию, никак не влияет на результат, поскольку НМТ допускает даже в том случае,если найдена всего одна удовлетворяющая подстановка.Вычислить значение формулы с помощью многоленточной НМТ легко за время O(n2).Таким образом, весь процесс распознавания ВЫП многоленточной НМТ занимает времяO(n2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
