Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 102
Текст из файла (страница 102)
Остальные части, Ф и Р, зависят только от М и и— длины входа и. Итак, для всякой НМТ М с полиномиальным временем работы р(п) можно построить алгоритм, который, получая на вход цепочку зу длины и, выдает Ем„,. Время работы такого алгоритма на многоленточной недетерминированной МТ есть О(рз(п)), а многоленточную МТ, в свою очередь, можно преобразовать в одноленточную МТ со временем работгя 0(р"(и)). Выходом данного алгоритма является булева формула Емки выполнимая тогда и только тогда, когда М допускает и в пределах первых р(п) переходов.
(.) Для того чтобы подчеркнуть исключительную значимость теоремы Кука, рассмотрим применение к ней теоремы!0.5. Допустим, что экземпляры ВЫП могли бы распознаваться некоторой НМТ за полиномиальное время, скажем, фп). Тогда всякий язык, допускаемый некоторой НМТ М за полиномиальное время р(п), допускался бы за полиномиальное время ДМТ, структура которой представлена на рис.
10.5. Вход зу машины М преобразуется в булеву формулу Ем„,. Затем эта формула подается на вход машины, распознающей ВЫП, и ответ, который она выдает для входа Ем, будет ответом нашего ал- горитма для входа и . да нет Рис. ?0.5. Если ВЬ??? принадлежит Р, то принадлежность Рпроизвальноголзыка из ЛгРможет бьипь доказана с помощью ДМТ указанного здесь вида ГЛАВА 10.
'ГРУДНОРЕ!ШАЕМЫЕ ПРОБЛЕМЫ 444 „10.2.4. Упражнения к разделу 10.2 10,24. Сколько удовлетворяющих подстановок имеют следующие формулы? Какие из них принадлежат ВЫП? а) |ь) х л (у м х) л (х ч -у); б) (хну) л(-(х ох) г( — хл. у)) 10.2.2. (1)рассмотрим граф 0 с четырьмя узлами: 1, 2, 3 и 4. Пусть х, где 1 <1<) < 4, — б>лева переменная, интерпретируемая как высказывание: "существует ребро, соединяющее узлы 1 ну".
Всякий граф, содержащий эти четыре узла, можно представить некоторой подстановкой. Например, граф, изображенный на рис. 10.1, представляется подстановкой, где х„имеет значение "ложь", а остальные переменные — "истина". Всякое свойство графа, касающееся только наличия или отсутствия тех или иных ребер, можно описать с помощью булевой формулы, истинной тогда и только тогда, когда подстановка описывает граф с данным свойством. Запишите формулы для следующих свойств: а) (ь) б имеет гамильтонов цикл; б) б — связный; в) О содержит клику размера 3 (треугольник), т.е. множество из трех узлов, каждые два из которых связаны ребром; г) б содержит хотя бы один изолированный узел |не имеюгпий ребер).
10.3. Ограниченная проблема выполнимости Мы планируем доказать ХР-полноту целого ряда проблем, таких как ПКОМ, упоминаемая в разделе 10.1.4. Это можно сделать с помошью сведения проблемы ВЫП к каждой интересуюшей нас проблеме. Однако сушествует промежуточная проблема, называемая "ЗВЫП", которую намного проше свести к типичным проблемам, чем ВЫП. В проблеме ЗВЫП речь по-прежнему идет о выполнимости булевых формул (выражений), ио эти выражения имеют строго определенный вид: они представляют собой логическое И "сумм", каждая из которых является логическим ИЛИ ровно трех переменных или их отрицаний. В этом разделе вводится ряд важных терминов, относяшихся к булевым формулам.
Затем выполнимость формулы произвольного вида сводится к выполнимости выражения в форме, нормальной для проблемы ЗВЪ!П. Отметим, что всякая булева формула Е имеет эквивалентное выражение Е в З-КНФ, но размер Е может экспоненциально зависеть от размера Е. Поэтому по сравнению с обычными для булевой алгебры преобразованиями полиномиальное сведение ВЫП к проблеме ЗВЫП должно быть более тонким. Всякую 10.3. ОГРАНИЧЕННАЯ ПРОБЛЕМА ВЫПОЛНИМОСТИ 445 формулу Е из ВЫП нужно преобразовать в формулу Р, находящуюся в З-КНФ, но Р не обязательно должна быть эквивалентной Е.
Достаточно убеди~ься, что Р выполнима тогда и только иногда, когда выполнима Е. 10.3.1. Нормальные формы булевых выражений Дадим три основных определения. ° Литералом является либо переменная, либо отрицание переменной. Например, х или — у. Для краткости вместо литерала вида -у часто используется переменная с чертой сверху, 1 . ° Дизъюнктом называется логическое ИЛИ одного нли нескольких литералов, например х, х чу, х ч — уч х. ° Говорят, что формула записана в конвюнктиенай нормальной форме (КНФ) (здесь замысловатый термин "конъюнкция'* обозначает логическое И), если представляет собой логическое И дизъюнктов. Для придания записываемым выражениям большей компактности примем альтернативные обозначения.
Оператор ч рассматривается как сложение, и вместо него используется оператор +, а л — как умножение, знак которо~о обычно опускается. Сомножители записываются рядом, как при конкатенации в регулярных выражениях. Тогда дизъюнкт естественно называть "суммой литералов*', а КНФ вЂ” "произведением дизъюнктов (сумм)".
Пример 10.10. В сжатых обозначениях формула (х ч у) л ( х ч х) имеет вид (х+у )(х+ х). Она записана в КНФ, так как представляет собой логическое И (произ- ведение) сумм (х + у ) и ( х + х), Формула(х+уй)(х+у+х)(т+Р) не находится в КНФ. Оиа представляет собой логическое И трех сумм (к+у Р ), (х+ у+ г) и ( у + Р ), однако первая из них — не дизь- юнкт, так как является суммой литерала и произведения двух литералов. Формула хух находится в КНФ. Напомним, что дизъюнкг может состоять и из одногоедииственного ли~врала.
Таким образом, наша формула представляет собой произведние трех дизъюнктов: (х), (у) и (х). П Говорят, что формула записана в к-конъюнктивной нормальной форме (й-КНФ), если представляет собой произведение дизъюнктов, каждый из которых является суммой ровно к различных литералов. Например, формула (х+ г )(у+ Р)(к+х ) записана в 2-КНФ, так как каждый из ее дизъюнктов содержит ровно два литерала. Все эти условия, накладываемые на булевы формулы, приводят к собственным проблемам выполнимости формул, удовлетворяющих этим условиям. Таким образом, мы будем говорить о следующих проблемах. ° Проблема ВКНФ: выполнима ли данная булева формула, записанная в КНФ? ° Проблема к-ВЫП: выполнима ли данная булева формула, находящаяся в к-КНФ? ГЛАВА 10.
ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ Обработка плохих входов Каждая рассмотренная проблема (ВЪ|П, ВКНФ, ЗВЫП и т.д.) — это язык с фиксированным алфавитом из восьми символов, цепочки которого иногда можно интерпретировать как булевы формулы. Цепочка, которую нельзя интерпретировать как булеву формулу, не может принадлежать языку ВЫП, Аналогично, если рассматриваются формулы ограниченного вида, то цепочка, представляюшая собой правильную булеву формулу, но не выражение требуемого вида, не может принадлежать данному языку. Например, алгоритм, решаюьций проблему ВКНФ, выдаст ответ "нет", если ему на вход подать булеву формулу, которая выполнима, но не находится в КНФ.
Мы увидим, что проблемы ВЫП, ЗВЫП и |в-ВЪ|П при 1 > 3 ХР-полны, но для проблем |ВЫП и 2ВЫП сушествуют алгоритмы с линейным временем работы. 10.3.2. Преобразование формул в КНФ Две булевы формулы называются эхвивалепьппыми, если имеют одно и то же значение при любой подстановке. Если две формулы эквивалентны, то они либо обе выполнимы, либо обе невыполнимы. Поэтому, на первый взгляд, преобразование произвольных формул в эквивалентные формулы, записанные в КНФ, позволило бы разработать метод полиномнального сведения ВЪ|П к ВКНФ. Это сведение свидетельствовало бы об ХР-полноте ВКНФ. Однако не все так просто.
Мы действительно можем преобразовать всякую формулу в КНФ, но время этого преобразования может оказаться больше полиномиального. В частности, при таком преобразовании длина формулы может вырасти экспоненциально, и тогда, безусловно, время порождения выхода также экспоненциально возрастет. К счастью, приведение произвольной булевой формулы к КНФ вЂ” это лишь один из возможных способов сведения ВЫП к ВКНФ, и доказательства, таким образом, ХР-полноты ВКНФ.
В действительности досвпточпо взять экземпляр ВЫП Е и преобразовать его в экземпляр ВКНФ Е, выполнимый тогда и только тогда, когда выполним Е. Формулы Е и Е могут быть неэквивалентными. Не требуется даже, чтобы множества переменных Е и Е совпадали; множество переменных Е будет, как правило, надмножеством множества переменных Е. Сведение ВЫП к ВКНФ состоит из двух частей.
На первом этапе все отрицания ~ "спускаются" вниз по дереву выражения, так что в формуле присутствуют только отрицания переменных. Булева формула преврашается в логическое И и ИЛИ литералов. Это преобразование дает формулу, эквивалентную исходной, и занимает время, как максимум, квадратичное относительно длины этой формулы. При реализации на обычном компьютере с тщательно выбранной структурой данных это преобразование требует линейного времени. з С обшнм набором переменных.
— Прим. перев. 10.3. ОГРАНИЧЕННАЯ ПРОБЛЕМА ВЫПОЛНИМОСТИ Второй этап — переписать формулу, которая представляет собой логическое И и ИЛИ литералов, в виде произведения дизъюнктов, т.е. привести ее к КНФ. Введение новых переменных позволяет провести это преобразование за время, полиномиально зависящее от размера исходной формулы. Новая формула Р; вообще говоря, не будет эквивалентна старой формуле Е. Но Р будет выполнима тогда и только тогда, когда выполнима Е. Точнее, если Т вЂ” некоторая подстановка, для которой Е истинна, то существует расширение Т, скажем 5, для которого истинна Р.
Расширение 5 подстановки Т вЂ” это подстановка, приписывающая переменным Т те же значения, что и Т, и, кроме того, в ней есть переменные, которых не было в Т. На первом этапе нужно спустить операторы ~ ниже операторов л и е. Для этого ис- пользуются следуюшие правила.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
