dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 100
Текст из файла (страница 100)
Таким образом, длина Ni есть O(p(n)), а длина N —O(p2(n)). Более важно то, что формулу N можно записать на ленту многоленточной МТза время, пропорциональное ее длине, и это время полиномиально зависит от n — длиныцепочки w.Çàâåðøåíèå äîêàçàòåëüñòâà òåîðåìû ÊóêàКонструкция формулыEM,w = S ∧ N ∧ Fбыла описана как функция, зависящая и от M, и от w, но в действительности только частьS — “правильный старт” — зависит от w, причем зависимость эта очень простая (w находится на ленте начального МО). Остальные части, N и F, зависят только от M и n —длины входа w.Итак, для всякой НМТ M с полиномиальным временем работы p(n) можно построить алгоритм, который, получая на вход цепочку w длины n, выдает EM,w.
Время работы такого алгоритма на многоленточной недетерминированной МТ есть O(p2(n)), амноголенточную МТ, в свою очередь, можно преобразовать в одноленточную МТ современем работы O(p4(n)). Выходом данного алгоритма является булева формула EM,w,выполнимая тогда и только тогда, когда M допускает w в пределах первых p(n) переходов.
Для того чтобы подчеркнуть исключительную значимость теоремы Кука, рассмотримприменение к ней теоремы 10.5. Допустим, что экземпляры ВЫП могли бы распознаваться некоторой НМТ за полиномиальное время, скажем, q(n). Тогда всякий язык, допускаемый некоторой НМТ M за полиномиальное время p(n), допускался бы за полиномиальное время ДМТ, структура которой представлена на рис. 10.5. Вход w машины Mпреобразуется в булеву формулу EM,w. Затем эта формула подается на вход машины, распознающей ВЫП, и ответ, который она выдает для входа EM,w, будет ответом нашего алгоритма для входа w.ПолиномиальныйпреобразовательдляАлгоритмрешенияВЫПРис. 10.5. Если ВЫП принадлежит P, то принадлежность P произвольного языкаиз NP может быть доказана с помощью ДМТ указанного здесь вида444Стр.
444ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛ10.2.4. Óïðàæíåíèÿ ê ðàçäåëó 10.210.2.1. Сколько удовлетворяющих подстановок имеют следующие формулы? Какие изних принадлежат ВЫП?а) (∗) x ∧ (y ∨ ¬x) ∧ (z ∨ ¬y);б) (x ∨ y) ∧ (¬(x ∨ z) ∨ (¬z∧¬y)).10.2.2. (!) Рассмотрим граф G с четырьмя узлами: 1, 2, 3 и 4. Пусть xij, где1 ≤ i < j ≤ 4, — булева переменная, интерпретируемая как высказывание:“существует ребро, соединяющее узлы i и j”. Всякий граф, содержащий этичетыре узла, можно представить некоторой подстановкой.
Например, граф,изображенный на рис. 10.1, представляется подстановкой, где x14 имеет значение “ложь”, а остальные переменные — “истина”. Всякое свойство графа,касающееся только наличия или отсутствия тех или иных ребер, можно описать с помощью булевой формулы, истинной тогда и только тогда, когда подстановка описывает граф с данным свойством.
Запишите формулы для следующих свойств:а) (∗) G имеет гамильтонов цикл;б) G — связный;в) G содержит клику размера 3 (треугольник), т.е. множество из трех узлов, каждые два из которых связаны ребром;г) G содержит хотя бы один изолированный узел (не имеющий ребер).10.3. Îãðàíè÷åííàÿ ïðîáëåìà âûïîëíèìîñòèМы планируем доказать NP-полноту целого ряда проблем, таких как ПКОМ, упоминаемая в разделе 10.1.4.
Это можно сделать с помощью сведения проблемы ВЫП к каждой интересующей нас проблеме. Однако существует промежуточная проблема, называемая “3ВЫП”, которую намного проще свести к типичным проблемам, чем ВЫП. Впроблеме 3ВЫП речь по-прежнему идет о выполнимости булевых формул (выражений),но эти выражения имеют строго определенный вид: они представляют собой логическоеИ “сумм”, каждая из которых является логическим ИЛИ ровно трех переменных или ихотрицаний.В этом разделе вводится ряд важных терминов, относящихся к булевым формулам.Затем выполнимость формулы произвольного вида сводится к выполнимости выраженияв форме, нормальной для проблемы 3ВЫП.
Отметим, что всякая булева формула E имеетэквивалентное выражение F в 3-КНФ, но размер F может экспоненциально зависеть отразмера E. Поэтому по сравнению с обычными для булевой алгебры преобразованиямиполиномиальное сведение ВЫП к проблеме 3ВЫП должно быть более тонким. Всякую10.3. ÎÃÐÀÍÈ×ÅÍÍÀß ÏÐÎÁËÅÌÀ ÂÛÏÎËÍÈÌÎÑÒÈСтр. 445445формулу E из ВЫП нужно преобразовать в формулу F, находящуюся в 3-КНФ, но F необязательно должна быть эквивалентной E. Достаточно убедиться, что F выполнима тогда и только тогда, когда выполнима E.10.3.1. Íîðìàëüíûå ôîðìû áóëåâûõ âûðàæåíèéДадим три основных определения.• Литералом является либо переменная, либо отрицание переменной. Например, xили ¬y. Для краткости вместо литерала вида ¬y часто используется переменная счертой сверху, y .• Дизъюнктом называется логическое ИЛИ одного или нескольких литералов, например x, x ∨ y, x ∨ ¬y ∨ z.• Говорят, что формула записана в конъюнктивной нормальной форме (КНФ)(здесь замысловатый термин “конъюнкция” обозначает логическое И), если представляет собой логическое И дизъюнктов.Для придания записываемым выражениям большей компактности примем альтернативные обозначения.
Оператор ∨ рассматривается как сложение, и вместо него используетсяоператор +, а ∧ — как умножение, знак которого обычно опускается. Сомножители записываются рядом, как при конкатенации в регулярных выражениях. Тогда дизъюнкт естественно называть “суммой литералов”, а КНФ — “произведением дизъюнктов (сумм)”.Пример 10.10. В сжатых обозначениях формула (x ∨ ¬y) ∧ (¬x ∨ z) имеет вид(x + y )( x + z). Она записана в КНФ, так как представляет собой логическое И (произведение) сумм (x + y ) и ( x + z).Формула (x + y z )(x + y + z)( y + z ) не находится в КНФ.
Она представляет собой логическое И трех сумм (x + y z ), (x + y + z) и ( y + z ), однако первая из них — не дизъюнкт, так как является суммой литерала и произведения двух литералов.Формула xyz находится в КНФ. Напомним, что дизъюнкт может состоять и из одногоединственного литерала. Таким образом, наша формула представляет собой произведение трех дизъюнктов: (x), (y) и (z). Говорят, что формула записана в k-конъюнктивной нормальной форме (k-КНФ), еслипредставляет собой произведение дизъюнктов, каждый из которых является суммой ровно k различных литералов. Например, формула (x + y )(y + z )(z + x ) записана в 2-КНФ,так как каждый из ее дизъюнктов содержит ровно два литерала.Все эти условия, накладываемые на булевы формулы, приводят к собственным проблемам выполнимости формул, удовлетворяющих этим условиям.
Таким образом, мыбудем говорить о следующих проблемах.• Проблема ВКНФ: выполнима ли данная булева формула, записанная в КНФ?• Проблема k-ВЫП: выполнима ли данная булева формула, находящаяся в k-КНФ?446Стр. 446ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛÎáðàáîòêà ïëîõèõ âõîäîâКаждая рассмотренная проблема (ВЫП, ВКНФ, 3ВЫП и т.д.) — это язык с фиксированным алфавитом из восьми символов, цепочки которого иногда можно интерпретировать как булевы формулы. Цепочка, которую нельзя интерпретировать как булеву формулу, не может принадлежать языку ВЫП. Аналогично, если рассматриваютсяформулы ограниченного вида, то цепочка, представляющая собой правильную булевуформулу, но не выражение требуемого вида, не может принадлежать данному языку.Например, алгоритм, решающий проблему ВКНФ, выдаст ответ “нет”, если ему навход подать булеву формулу, которая выполнима, но не находится в КНФ.Мы увидим, что проблемы ВЫП, 3ВЫП и k-ВЫП при k > 3 NP-полны, но для проблем1ВЫП и 2ВЫП существуют алгоритмы с линейным временем работы.10.3.2.
Ïðåîáðàçîâàíèå ôîðìóë â ÊÍÔДве булевы формулы3 называются эквивалентными, если имеют одно и то же значение при любой подстановке. Если две формулы эквивалентны, то они либо обе выполнимы, либо обе невыполнимы. Поэтому, на первый взгляд, преобразование произвольных формул в эквивалентные формулы, записанные в КНФ, позволило бы разработатьметод полиномиального сведения ВЫП к ВКНФ. Это сведение свидетельствовало бы обNP-полноте ВКНФ.Однако не все так просто.
Мы действительно можем преобразовать всякую формулув КНФ, но время этого преобразования может оказаться больше полиномиального. В частности, при таком преобразовании длина формулы может вырасти экспоненциально, итогда, безусловно, время порождения выхода также экспоненциально возрастет.К счастью, приведение произвольной булевой формулы к КНФ — это лишь один извозможных способов сведения ВЫП к ВКНФ, и доказательства, таким образом, NP-полноты ВКНФ. В действительности достаточно взять экземпляр ВЫП E и преобразоватьего в экземпляр ВКНФ F, выполнимый тогда и только тогда, когда выполним E. Формулы E и F могут быть неэквивалентными. Не требуется даже, чтобы множества переменных E и F совпадали; множество переменных F будет, как правило, надмножествоммножества переменных E.Сведение ВЫП к ВКНФ состоит из двух частей.
На первом этапе все отрицания ¬“спускаются” вниз по дереву выражения, так что в формуле присутствуют только отрицанияпеременных. Булева формула превращается в логическое И и ИЛИ литералов. Это преобразование дает формулу, эквивалентную исходной, и занимает время, как максимум, квадратичное относительно длины этой формулы. При реализации на обычном компьютере с тщательно выбранной структурой данных это преобразование требует линейного времени.10.3. ÎÃÐÀÍÈ×ÅÍÍÀß ÏÐÎÁËÅÌÀ ÂÛÏÎËÍÈÌÎÑÒÈСтр.
447447Второй этап — переписать формулу, которая представляет собой логическое И иИЛИ литералов, в виде произведения дизъюнктов, т.е. привести ее к КНФ. Введение новых переменных позволяет провести это преобразование за время, полиномиально зависящее от размера исходной формулы. Новая формула F, вообще говоря, не будет эквивалентна старой формуле E. Но F будет выполнима тогда и только тогда, когда выполнимаE.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
