dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 101
Текст из файла (страница 101)
Точнее, если T — некоторая подстановка, для которой E истинна, то существует расширение T, скажем S, для которого истинна F. Расширение S подстановки T — это подстановка, приписывающая переменным T те же значения, что и T, и, кроме того, в нейесть переменные, которых не было в T.На первом этапе нужно спустить операторы ¬ ниже операторов ∧ и ∨. Для этого используются следующие правила.1.¬(E ∧ F) ⇒ ¬(E) ∨ ¬(F).
Это правило — один из законов Де Моргана — позволяетспустить оператор ¬ под оператор ∧. Отметим, что в виде побочного эффекта ∧ меняется на ∨.2.¬(E ∨ F) ⇒ ¬(E) ∧ ¬(F). Другой “закон Де Моргана” позволяет спустить ¬ под оператор ∨, изменяемый на ∧.3.¬(¬(E)) ⇒ E. Этот закон двойного отрицания уничтожает пару операторов ¬, применяемых к одной формуле.Пример 10.11. Рассмотрим формулу E = ¬((¬(x + y))( x + y)). Заметим, что в ней пе-ремешаны оба используемых обозначения.
Оператор ¬ использован явно, когда формула, отрицание которой берется, состоит более чем из одной переменной. На рис. 10.6 показано, как формула переписывается шаг за шагом до тех пор, пока отрицания ¬ не станут составляющими литералов.ФормулаПравило¬((¬(x + y))( x + y))Начало¬(¬(x + y)) + ¬( x + y)(1)x + y + ¬( x + y)(3)x + y + (¬( x )) y(2)x+y+xy(3)Рис. 10.6. Спуск отрицаний вниз по дереву формулы так,чтобы они встречались только в литералах3448Стр. 448С общим набором переменных. — Прим.
перев.ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛЗаключительная формула эквивалентна исходной и состоит из логических связок И иИЛИ литералов. Ее можно упростить до формулы x + y, но это упрощение несущественно для нашего утверждения о том, что формулу можно переписать так, чтобы оператор ¬присутствовал только в литералах. Теорема 10.12. Всякая булева формула E эквивалентна формуле F, в которой отрицания присутствуют только в литералах, т.е. применяются непосредственно к переменным.Более того, длина F линейно зависит от количества символов в E, и F можно построитьпо E за полиномиальное время.Доказательство. Используем индукцию по числу операторов (∧, ∨ и ¬) в E. Покажем, что существует эквивалентная формула F, в которой ¬ присутствует только в литералах.
Кроме того, если E содержит n ≥ 1 операторов, то F содержит не более 2n – 1операторов.Поскольку формуле F достаточно одной пары скобок для каждого оператора, ачисло переменных в ней не может превышать числа операторов больше, чем на единицу, то приходим к выводу, что длина F линейно пропорциональна длине E.
Болееважно, как мы увидим, что время построения F пропорционально ее длине и, следовательно, — длине E.Базис. Если E содержит один оператор, то она должна иметь вид ¬x, x ∨ y или x ∧ y,где x и y — переменные. В каждом из этих случаев формула уже имеет требуемый вид,поэтому F = E. Отметим, что, поскольку и E, и F содержат по одному оператору, то соотношение “число операторов в F не превышает числа операторов в E, умноженного надва, минус один” выполняется.Индукция. Предположим, что утверждение справедливо для всех формул, числооператоров в которых меньше, чем в E.
Если верхний оператор в E — не ¬, то формуладолжна иметь вид E1 ∨ E2 или E1 ∧ E2. В любом из этих случаев гипотеза индукции применима к формулам E1 и E2, и согласно ей существуют эквивалентные формулы — F1 иF2, соответственно, — в которых ¬ встречается только в литералах.
Тогда F = F1 ∨ F2или F = (F1) ∧ (F2) служат подходящими эквивалентами для E. Пусть E1 и E2 содержатсоответственно a и b операторов. Тогда E содержит a + b + 1 операторов. Согласно гипотезе индукции F1 и F2 содержат соответственно 2a – 1 и 2b – 1 операторов. Таким образом, Fсодержит не более, чем 2a + 2b – 1 операторов, что не превосходит 2(a + b + 1) – 1, иличисла операторов в E, умноженного на два, минус 1.Рассмотрим теперь случай, когда E имеет вид ¬E1.
В зависимости от верхнего оператора в формуле E1 возможны три варианта. Заметим, что E1 содержит хотя бы один оператор, иначе E — формула из базиса.1.E1 = ¬E2. Тогда согласно закону двойного отрицания формула E = ¬¬(E2) эквивалентна E2. Гипотеза индукции применима, так как в E2 содержится меньше операторов, чем в E. Можно найти формулу F, эквивалентную E2, в которой отрицаниявстречаются только в литералах. Формула F годится и для E. Поскольку число опе-10.3. ÎÃÐÀÍÈ×ÅÍÍÀß ÏÐÎÁËÅÌÀ ÂÛÏÎËÍÈÌÎÑÒÈСтр.
449449раторов в F не превышает числа операторов в E2, умноженного на два, минус 1, тооно, конечно же, не превышает числа операторов в E, умноженного на два, минус 1.2.E1 = E2 ∨ E3. Согласно закону Де Моргана формула E = ¬(E2 ∨ E3) эквивалентна(¬(E2)) ∧ (¬(E3)). Обе формулы ¬(E2) и ¬(E3) содержат меньше операторов, чем E.Поэтому согласно гипотезе индукции существуют эквивалентные им формулы F2 иF3, в которых отрицания встречаются только в литералах.
Тогда эквивалентом Eслужит формула F = (F2) ∧ (F3). Кроме того, мы утверждаем, что число операторов вF не слишком велико. Пусть E2 и E3 содержат соответственно a и b операторов. Тогда в E содержится a + b + 2 операторов. Поскольку в формулах ¬(E2) и ¬(E3) соответственно a + 1 и b + 1 операторов, и формулы F2 и F3 построены по этим формулам,то согласно гипотезе индукции в F2 и F3 не больше, чем 2(a + 1) – 1 и 2(b + 1) – 1 операторов соответственно. Таким образом, F содержит не более 2a + 2b + 3 операторов, а это и есть число операторов в E, умноженное на два, минус 1.3.E1 = E2 ∧ E3.
Обоснование этой части, использующее второй закон Де Моргана, аналогично пункту 2.Îïèñàíèÿ àëãîðèòìîâФормально время работы алгоритма сведения есть время, необходимое для выполнения его на одноленточной машине Тьюринга, однако такие алгоритмы слишкомсложны. Мы знаем, что множества проблем, которые можно решить за полиномиальное время на обычных компьютерах, многоленточных и одноленточных МТ, совпадают, хотя степени полиномов при этом могут различаться. Таким образом, описываянекоторые по-настоящему сложные алгоритмы, требующие сведения одной NP-полной проблемы к другой, примем соглашение, что время сведения будет ограниченовременем работы его эффективной реализации на обычном компьютере.
Это избавитнас от подробностей обработки лент и позволит выделить по-настоящему важные алгоритмические идеи.10.3.3. NP-ïîëíîòà ïðîáëåìû ÂÊÍÔТеперь нам необходимо привести к КНФ формулу E, которая состоит из логическихИ и ИЛИ литералов. Как уже упоминалось, чтобы за полиномиальное время создать поE формулу F, выполнимую тогда и только тогда, когда выполнима E, нужно отказатьсяот преобразования, сохраняющего эквивалентность формул, и ввести в F новые переменные, отсутствующие в E.
Используем этот прием в доказательстве теоремы об NP-полнотепроблемы ВКНФ, а затем приведем пример его применения.Теорема 10.13. Проблема ВКНФ NP-полна.450Стр. 450ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛДоказательство. Покажем, как свести ВЫП к ВКНФ за полиномиальное время. Вначале с помощью метода, описанного в теореме 10.12, преобразуем данный экземплярВЫП в формулу E, содержащую ¬ только в литералах.
Затем покажем, как за полиномиальное время преобразовать E в КНФ-формулу F, выполнимую тогда и только тогда, когда выполнима E. Формула F строится индуктивно по длине E, а ее конкретные свойства — это даже больше, чем нам нужно. Точнее, индукцией по числу вхождений символовв E (“длине”) докажем следующее утверждение.• Пусть E — булева формула длины n, в которой ¬ встречается только в литералах.Тогда существуют константа c и формула F, удовлетворяющие утверждениям:а) F находится в КНФ, и содержит не более n дизъюнктов;б) F можно построить по E за время, не превышающее c|E|2;в) подстановка T для E делает E истинной тогда и только тогда, когда существует расширение S подстановки T, удовлетворяющее формуле F.Базис.
Если E состоит из одного или двух символов, то оно — литерал. Литерал является дизъюнктом, поэтому E уже находится в КНФ.Индукция. Предположим, что всякую формулу, более короткую, чем E, можно преобразовать в произведение дизъюнктов, и для формулы длиной n это преобразование занимает время не более cn2. В зависимости от верхнего оператора E возможны два варианта.Вариант 1. E = E1 ∧ E2. Согласно гипотезе индукции существуют формулы F1 и F2,которые выводятся из E1 и E2, соответственно, и находятся в КНФ.
Все подстановки,удовлетворяющие E1, и только они, могут быть расширены до подстановок, удовлетворяющих F1. То же самое верно для E2 и F2. Не теряя общности, можно предполагать, чтопеременные в F1 и F2 различны, за исключением переменных, присутствующих в E, т.е.вводимые в F1 и/или F2 переменные выбираются различными.Рассмотрим F = F1 ∧ F2. Очевидно, что формула F1 ∧ F2 находится в КНФ, если в КНФнаходятся F1 и F2. Нам нужно показать, что подстановку T для формулы E можно расширить до подстановки, удовлетворяющей F, тогда и только тогда, когда T удовлетворяет E.(Достаточность) Пусть T удовлетворяет E.
Пусть T1 и T2 — сужения подстановки T,применяемые только к переменным формул E1 и E2, соответственно. Тогда согласно индуктивной гипотезе T1 и T2 могут быть расширены до подстановок S1 и S2, удовлетворяющих F1 и F2, соответственно. Пусть S — подстановка, согласованная с S1 и S2, т.е.приписывает переменным те же значения, что S1 и S2. Заметим, что лишь переменные изE присутствуют и в F1, и в F2, поэтому подстановки S1 и S2 согласованы на переменных,на которых обе они определены, и построить S всегда возможно. Но тогда S есть расширение T, удовлетворяющее F.(Необходимость) Наоборот, пусть подстановка T имеет расширение S, удовлетворяющее F.
Пусть T1 (T2) — сужение T на переменные E1 (E2). Сужение S на переменныеF1 (F2) обозначим через S1 (S2). Тогда S1 — это расширение T1, а S2 — расширение T2.10.3. ÎÃÐÀÍÈ×ÅÍÍÀß ÏÐÎÁËÅÌÀ ÂÛÏÎËÍÈÌÎÑÒÈСтр. 451451Поскольку F есть логическое И формул F1 и F2, S1 должна удовлетворять формуле F1, аS2 — формуле F2. Согласно гипотезе индукции T1 (T2) должна удовлетворять E1 (E2). Поэтому T удовлетворяет E.Вариант 2. E = E1 ∨ E2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
