А.А. Сапоженко - Некоторые вопросы сложности алгоритмов (PDF) (1132758), страница 6
Текст из файла (страница 6)
КНФ K 0 , возможно, содержит скобки вида(y ∨ y) и (y ∨ ȳ), а также скобки, отличающиеся лишь порядком слагаемых.Удаление этих вхождений можно осуществить за число шагов, не превосходящее O(L21 ), где L1 длина W (K 0 ), а, значит, не более чем за O(L4 ) шагов,где L — число букв в W (K).Поскольку число переходов не превосходит n − 2 ≤ L, то для преобразования исходной КНФ в формулу, зависящую не более, чем от одной переменной, достаточно O(L5 ) шагов.В случае, когда КНФ K зависит не более, чем от одной переменной, возможны следующие случаи: K = x, K = x̄, K = x ∨ x̄, K = x&x̄. Ясно, чтоответ на вопрос о выполнимости в этом случае получается за O(1) шагов.Таким образом, распознавание выполнимости 2-КНФ осуществимо за O(L5 )шагов на детерминированной машине Тьюринга.2Теорема 5.3 3-ВЫП является N P -полной.Доказательство. Покажем, что задача ВЫП полиномиально сводится кзадаче 3-ВЫП.
Для этого укажем, как преобразовать произвольную КНФ Kв 3-КНФ K 0 , выполнимую тогда и только тогда, когда КНФ K выполнима.Пусть С = y1 ∨ ... ∨ ym — скобка, являющаяся сомножителем КНФ K,и m > 3. Обозначим через K1 КНФ, полученную из K вычеркиванием скобки C. Пусть u — переменная, не входящая в K. Положим D = (y1 ∨ y2 ∨u)(y3 ∨ ... ∨ ym ∨ ū). Покажем, что КНФ K выполнима тогда и только тогда,когда КНФ D&K1 выполнима.e = (α1 , ..., αn ) — набор, обращающий КНФ K в единицу. ПоложимПусть αe ∨ h(α)e = 1.g(x1 , ..., xn ) = y1 ∨ y2 и h(x1 , ..., xn ) = y3 ∨ ... ∨ ym .
Тогда g(α)e = 1, то набор βe = (α1 , ..., αn , 0) обращает КНФ D&K1 в единицуЕсли g(α)e = 0,(последняя координата набора βe есть значение переменной u). Если g(α)eто набор β = (α1 , ..., αn , 1) обращает КНФ D&K1 в единицу.Пусть теперь βe = (α1 , ..., αn , β) — набор, обращающий КНФ D&K1 вe = 1 и D&K1 (α)e = 1, а, значит,единицу. Пусть сначала β = 0. Тогда g(α)e = 1.
Если же β = 1, то h(α)e = 1 и D&K1 (α)e = 1.K(α)Указанное выше преобразование КНФ K в КНФ D&K1 уменьшает наединицу число букв в скобке C и увеличивает общее число букв на 2. Пустьm1 , ..., mk — числа букв в скобках КНФ K и mi > 3. Тогда достаточно добавить аналогичным способом не более 2(m1 + ... + mk − 3k) букв с тем, чтобыполучить 3-КНФ K ∗ , выполнимую тогда и только тогда, когда КНФ K выполнима.Полиномиальность преобразования очевидна.228Упражнение. Доказать N P -полноту задачи 4-ВЫП.Задача ТАВТОЛОГИЯ определяется следующим образом.ВХОД: ДНФ D = D(x1 , . . . , xn ).СВОЙСТВО: D(α1 , .
. . , αn ) = 1 для всякого набора (α1 , . . . , αn ).Упражнение. Доказать N P -полноту задачи ТАВТОЛОГИЯ.Список литературы[1] Кибернетический Сборник No 12 (Нов. серия), М. МИР, 1975, С. 5–38.[2] А. Ахо, Д. Хопкрофт, Д. Ульман// Построение и анализ вычислительныхалгоритмов, М., Мир, — 1979. — С. 420–428.296Некоторые N P -полные задачиВ этом параграфе расширяется список N P -полных задач. Доказывается N P полнота задач 0-1 ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ, КЛИКА,ВЕРШИННОЕ ПОКРЫТИЕ, ПОКРЫТИЕ МНОЖЕСТВ, РАСКРАСКА.
Доказательство N P -полноты очередной задачи проводится путем сведения кней одной из уже известных N P -полных задач. Сведение состоит в преобразовании входов некоторой задачи во вход исследуемой задачи с условием,что соответствующие свойства одновременно выполняются или не выполняются для рассматриваемых задач. Принадлежность задач классу N P , какправило, является очевидной и не доказывается. Полиномиальность преобразования входов также легко усматривается.
Ниже (см. рис. 4) дана схемасведения задач.Рис.4Задача 0-1 ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ (0-1 ЦЛП):ВХОД: Матрица А = (ai,j ), размера p × n, и целочисленный векторb = (b1 , ..., bp ).СВОЙСТВО: Cуществует 0-1-вектор x = (x1 , ..., xn ) такой, чтоAxT ≥ bT .(16)Теорема 6.1 ВЫП ≺ 0-1 ЦЛП.Доказательство.Пусть K = C1 &...&Cp — произвольная КНФ с p скобками, зависящая отпеременных x1 , . .
. , xn . Для i = 1, . . . , p, j = 1, . . . , n положим1, если xi ∈ Cj ,aij = −1, если x̄i ∈ Cj ,0, иначе30иbi = 1− число отрицаний переменных в Ci .Очевидно, что вход задачи 0-1 ЦЛП можно задать словом длины, не превосходящей O(np), а преобразование записи КНФ K в запись входа задачи0-1 ЦЛП можно осуществить на детерминированной машине Тьюринга заполиномиальное время от длины записи КНФ K.Покажем, что 0-1-вектор x = (x1 , ..., xn ), удовлетворяющий (16), существует тогда и только тогда, когда КНФ K выполнима.Достаточность.
Пусть K выполнима. Тогда существует набор α̃ =(α1 , ..., αn ) значений переменных такой, что K(α̃) = 1. Обозначим через Aiстроку (ai1 , . . . , ain ) матрицы A. Покажем, что (16) выполнено при x = α̃.Для этого убедимся, что для всякого i = 1, . . . , p выполнено(Ai , x) ≥ bi = 1 − число отрицаний переменных в Ci .(17)В самом деле, скобка Ci обращается на наборе α̃ в 1. Это означает, что либо существует переменная из Ci , обращающаяся в 1, либо в Ci существуетотрицание некоторой переменной, обращающейся в 0. В первом случае минимальное значение скалярного произведения (Ai , x) достигается в случае,когда все координаты xj при коэффициентах aij , равных 1, за исключением одного, обращаются в 0, а все координаты xj при коэффициентах aij ,равных -1, обращаются в 1.
Во втором случае минимальное значение скалярного произведения (Ai , x) достигается в случае, когда все координаты xjпри коэффициентах aij , равных 1, обращаются в 0, а все координаты xj прикоэффициентах aij , равных -1, за исключением одного, обращаются в 1. Вобоих случаях (17) удовлетворяется.Необходимость.
Пусть существует двоичный вектор x = (x1 , ..., xn ),удовлетворяющий (16). Покажем, что K(x) = 1, а, значит, КНФ K выполнима. Из (16) следует, что (17) выполнено для всякого i = 1, . . . , p. Отсюдавытекает, что все скобки КНФ K содержат хотя бы одну букву, обращающуюся в 1 на наборе x = (x1 , ..., xn ).2Пример. Для КНФ K = (x1 ∨ x2 )&(x̄1 ∨ x̄2 ∨ x3 ) входом соответствующейзадачи 0-1 ЦЛП являются матрицаÃA=11 0−1 −1 1!и вектор b = (1, −1).
Решением неравенства (16) являются векторы (0, 1, α),(1, 0, β) и (1, 1, 1), где α, β ∈ {0, 1}. Они же обращают КНФ K в единицу.31Задача КЛИКА:ВХОД: Граф G = (V, E), число k.СВОЙСТВО: В G существует полный подграф с k вершинами (k-клику).Теорема 6.2 В Ы П ≺ К Л И К А.Доказательство.Пусть КНФ K = C1 &...&Cq является конъюнкцией некоторых q скобок, гдеCi = (yi1 ∨ ... ∨ yiki ), а yij — некоторая буква. ПоложимV = {< y, i >: y есть буква из Ci , 1 ≤ i ≤ q};E = {{< y, i >, < z, j >} : i 6= j, y 6= z̄};k = q.Число вершин графа G не превосходит nq, а число ребер не превосходит(nq)2 .
Поэтому вход задачи КЛИКА можно закодировать словом, длина которого ограничена полиномом от длины записи КНФ K. Ясно также, чтосуществует машина Тьюринга, преобразующая запись КНФ K в запись графа G, и числа k за полиномиальное от длины записи КНФ K время.Покажем, что определенный выше граф G содержит q-клику тогда и только тогда, когда КНФ K выполнима.Достаточность.
Пусть K выполнима. Тогда существует набор α̃ =(α1 , ..., αn ) значений переменных такой, что K(α̃) = 1. Каждая скобка обращается на этом наборе в 1. Следовательно, всякая скобка Ci содержит хотя быодну букву, принимающую значение 1. Пусть для Ci такой буквой будет yi .Убедимся в том, что множество вершин {< yi , i >}, i = 1, ..., q, порождаетполный подграф в G. Если не так, то найдутся такие i и j, что i 6= j ивершины < yi , i > и < yj , j > не смежны в графе G.
Тогда yi = ȳj . Но этоневозможно в силу выбора букв yi .Необходимость. Пусть G содержит q-клику. Вторые компоненты вершин, образующих клику, попарно различны, ибо вершины с равными вторыми компонентами не смежны в графе G. Следовательно, вершины кликивзаимно однозначно соответствуют скобкам КНФ K. Пусть вершины кликиимеют вид < yi , i >, i = 1, ..., q. Обозначим через S (через S̄) множество техбукв yi , которые являются переменными (соответственно, отрицаниями переменных). Ясно, что S ∩ S̄ = ∅, ибо в противном случае некоторые вершинывида < yi > и < yj , j >, такие, что yi = ȳj , были смежны в графе G.
Еслиположить все переменные из S равными 1, а переменные из S̄ равными 0, токаждая скобка Ci обратится в 1. Значит, КНФ K выполнима.232Пример. Для КНФ K = (x1 ∨ x2 )&(x̄1 ∨ x̄2 ∨ x3 ) входом соответствующейзадачи КЛИКА являются граф G, показанный на рис. 5, и число 2.Рис.5Задача ВЕРШИННОЕ ПОКРЫТИЕ:ВХОД: Граф G0 = (V 0 , E 0 ), число l.СВОЙСТВО: Cуществует множество вершин R такое, что |R| ≤ l и приэтом каждое ребро графа G инцидентно некоторой вершине из R.Теорема 6.3 КЛИКА ≺ ВЕРШИННОЕ ПОКРЫТИЕ.Доказательство.Отображение входов имеет вид:G0 = (V 0 , E 0 ) есть дополнение графа G = (V, E).l = |V | − k.Заметим, что множество A ⊆ V является кликой в G тогда и только тогда, когда V \ A является вершинным покрытием дополнения Ḡ этого графа.Действительно, если A — клика в G, то никакое ребро в Ḡ не соединяетникакие две вершины в A.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
