Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 100
Текст из файла (страница 100)
10.2.1. Проблема выполнимости Булевы формулы (выражения) строятся из следующих элементов. 1, Булевы переменные, принимающие значения 1 (нстина) или 0 (ложь). 2. Бинарные операторы л и ~, обозначающие логические связки И и ИЛИ двух формул. 3. Унарный оператор —, ко~орый обозначает логическое отрицание. 4. Скобки для группирования операторов и операндов, если необходимо изменить порядок старшинства (приоритетов) операторов, принятый по умолчанию (вначале применяется -, затем л и, наконец, ы). Пример 10.6. Примером булевой формулы является хл-(уме). Подформула уы имеет значение "истина", если истинна хотя бы одна из переменных у или х, и "ложь", если ГЛАВА 10.
'ГРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ 436 обе оии ложны. Большая подформула -(у ч г) истинна лишь тогда, когда у ч х ложно, т.е. когда обе переменные ложны. Если хотя бы одна из у или г истинна, то — (у ч х) ложно. Рассмотрим, наконец, всю формулу. Поскольку она представляет собой логическое И лаух подформул, то она истинна только тогда, когда истинны обе подформулы, т.е. хн- (у ч х) истинна тогда и только тогда, когда х истинна, а у и х ложны.
СЗ Выбрать подстановку (набор значений нареченных) для данной булевой формулы Š— значит приписать значение "истина" или "ложь" каждой из переменных, фигурирующих в Е. Значение формулы Е при данной подстановке Т, обозначаемое как Е(7),— зто результат вычисления Е, в которой каждая из ее переменных х заменена значением 7(х) ("истина" или "ложь"), которое соответствует х в Т. Формула Е истинна при подстановке Т„или подстановка Т удовлетворяет формуле Е, если Е(7) = 1, т.е. данная подстановка Т делает формулу Е истинной.
Булева формула Е называется выполнимой, если существует хотя бы одна подстановка Т, для которой Е истинна. Пример 10.7. Формула хп (и ч х) из примера 10.6 выполнима. Мы убедились, что эта формула истинна при подстановке Т, определенной равенствами Т(х)= 1, Т(у) =-0 и 7(з)=0, поскольку принимает значение !. Мы также заметили, что Т вЂ” единственная подстановка, удовлетворяющая этой формуле, поскольку для остальных семи комбинаций значений трех переменных формула ложна (принимает значение 0).
В качестве еше одного примера рассмотрим формулу Е = хо( х чу) п-у. Утверждаем, что Е невыполнима. Поскольку переменных в ней всего две, то число возможных подстановок есть 2' = 4, так что нетрудно проверить их и убедиться, что при всех формула Е принимает значение О. Однако это можно обосновать и по-другому.
Е истинна только тогда, когда все три члена, связанных л, истинны. Это значит, что х должно быть истинным (из-за первого члена), а у — ложным (из-за третьего члена). Но для такой подстановки значение среднего члена х чу ложно, Таким образом, значение Е не может быть истинным, и Е действительно невыполнима. В одном из рассмотренных примеров у формулы была лишь одна удовлетворяющая подстановка, а в другом их вообще не было. Существует также множество примеров, в которых у формулы есть более одной удовлетворяющей подстановки.
Например, рассмотрим г = х ч -у. Значение г есть ) для трех следующих подстановок. т (х) = 1; Т,(у) = 1. 2. Т:(х) = 1; Тз(у) = О. 3. Т,(х) = 0; Тз(у) = О. г" принимает значение 0 лишь для четвертой подстановки, где х = 0 и у = 1. Таким обра- зом, г выполнима. П Проблема выполнимости состоит в следующем. ° Выяснить, выполнима ли данная булева формула. 10ХЬ ПЕРВАЯ 1чР-ПОЛНАЯ ПРОБЛЕМА 437 Проблема выполнимости обычно обозначается как ВЫП. Если рассматривать ее как язык, то проблема ВЫП есть множество (закодированных) выполнимых булевых формул.
Цепочки, которые либо не образуют правильные коды булевых формул, либо являются кодами невыполнимых булевых формул, не принадлежат ВЫП. 10.2.2. Представление экземпляров ВЫП Символами в булевых формулах являются л, ~~, —,, левые и правые скобки, а также символы, представляющие переменные. Выполнимость формулы зависит не от имен переменных, а от того, являются ли два вхождения переменных одной и той же переменной или двумя разными. Таким образом, можно считать, что переменными явля- ются х„х„..., хотя в примерах в качестве имен переменных по-прежнему используется не только х, но и имена вроде у или ж Считается также, что переменные переименованы так, что используются наименьшие из возможных индексов.
Например, переменная хэ ие используется, если в той же формуле не использованы переменные х,-х,. Поскольку число переменных, встречающихся в булевых формулах, может быть бесконечным, то мы сталкиваемся с уже знакомой проблемой разработки кода, имеющего фиксированный конечный алфавит, для представления формул с произвольным, сколь угодно большим, числом переменных. Только имея такой код, можно говорить о ВЫП как о "проблеме", т.е, языке с фиксированным алфавитом, состоящем из кодов выполнимых булевых формул. Будем использовать следующий код. 1.
Символы л, ч, —, ( и ) представляют самих себя. 2. Переменная х, представляется символом х с дописанной к нему последовательностью нулей и единиц — двоичной записью числа С Таким образом, алфавит проблемы~языка ВЫП содержит всего восемь символов. Все экземпляры ВЫП являются цепочками символов в этом фиксированном конечном алфавите. Пример 10.8. Рассмотрим формулу х л (у ч г) из примера 10.6. Первое, что нужно сделать для ее кодирования, — заменить переменные индексированными символами х.
Поскольку переменных три, следует использовать хь х и х,. Выбор х, для замены переменных х, у и з зависит от нас. Положим для определенности х =хи у =ха и з = х,. Тогда формула принимаетвидх~ А (х,мхз), и ее кодом являетсях!л (х10чх!1). П Отметим, что длина закодированной булевой формулы примерно равна числу позиций в этой формуле, если считать каждое вхождение переменной за 1. Разница возникает из-за того, что если формула имеет гл позиций, то она может содержать 0(т) переменных„и для кодирования каждой из них может понадобиться О(1о8 гл) символов. Таким образом, формула длиной т позиций может иметь код длиной и = 0(т 1о8 га) символов.
Однако разница между и и т!ойгя, очевидно, ограничена полиномом. Поэтому, если нас интересует лишь, можно ли решить проблему за время, полиномиально зависящее от размера входных данных, то длину кода формулы и число позиций в ней различать не обязательно. ГЛАВА 10. 'ГРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ 438 10.2.3. 1з1Р-полнота проблемы ВЫП Докажем "теорему Кука", утверждающую, что ВЫП МР-полна.
Для доказательства, что некоторая проблема является ХР-полной, сначала нужно показать, что она принадлежат классу ЛГР, а затем — что к ней сводится любой язык из ЛT. Как правило, для довазательства второй части к нашей проблеме полиномиально сводится какая-либо другая ХР-полная проблема, а затем применяется теорема 10.5.
Но пока у нас нет ни одной ХР- полной проблемы, которую можно было бы свести к ВЫП. Поэтому нам остается только сводить каждую без исключения проблему из Лер к ВЫП. Теорема 10.9 (теорема Кука). Проблема ВЫП МР-полна. Доказательство. В первой части доказывается, что ВЫП принадлежит Л'Р. Сделать зтю довольно легко. 1. С помощью свойства недетерминированности НМТ для данной формулы Е угадываем подстановку Т. Если код Е имеет длину и, то многоленточной НМТ для этого достаточно времени О(и). Заметим, что у НМТ есть много возможностей выбора переходов, и по окончании процесса угадывания она может иметь 2' различных МО, где каждая ветка представляет угадывание отдельной подстановки.
2. Находим значение Е для подстановки Т. Если ЕЩ = 1, то допускаем. Отметим, что эта часть детерминирована. Тот факт, что другие ветки могут не приводить к допусканию, никак не влияет на результат, поскольку НМТ допускает даже в том случае, если найдена всего одна удовлетворяющая подстановка. Вычислить значение формулы с помощью многоленточной НМТ легко за время 0(п ). Таким образом, весь процесс распознавания ВЫП многоленточной НМТ занимает время 0(п'). Преобразование в одноленточную НМТ может возвести время в квадрат, так что одиоленточной НМТ будет достаточно времени О(п').
Теперь нужно доказать трудную часть — что для произвольного языка Ь из ЛР сушесвует полиномиальное сведение Е к ВЫП. Можно предположить, что существует некоторая одноленточная НМТ М и полином р(и), для которого М обрабатывает вход длиной и не более, чем за р(п) шагов вдоль любой ветки. Далее, ограничения, доказанные в теореме 8.12 для ДМТ, можно аналогично доказать и для НМТ. Поэтому можно предположить, что М никогда не печатает пробела и никогда не сдвигает головку левее ее исходной позиции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
