А.А. Сапоженко - Некоторые вопросы сложности алгоритмов, страница 6

Пусть КНФ K не содержит однобуквенных сомножителей.Тогда переход к K 0 осуществляется следующим образом. Выбираем некоторую букву x в КНФ K. Пусть K0 представляетсобой конъюнкцию всех дизъюнкций вида (x̄∨y), где y — некоторая буква, отличная от x и x̄, входящих в K, K1 представляетсобой конъюнкцию всех дизъюнкций вида (x ∨ z), входящих в K, а K2 представляетсобой конъюнкцию всех остальныхVдизъюнкций,входящихвK.Такимобразом,КНФKпредставимаввидеK=001≤i≤k (x̄ ∨ yi ), а K1 представима в видеVK1 = 1≤j≤m (x̄ ∨ zj ).

Заметим, чтоK0 K1 K2 = (x̄ ∨ y1 ...yk )(x ∨ z1 ...zm )K2 .(15)16Легко проверить, что формула (x̄ ∨ Y )(x ∨ Z), в которой Y и Z не зависят от x, выполнима тогда и только тогда, когдавыполнима формула Y ∨ Z. С учетом того, что K2 не зависит от x, аналогично получаем, что правая часть (15) выполниматогда и только тогда, когда выполнима формула^^(y1 ...yk ∨ z1 ...zm )K2 =(yi ∨ zj )K2 = K 0 .(16)1≤i≤k 1≤j≤mКНФ K 0 не содержит x и x̄, а число букв в ней не больше L2 , где L — число букв в W (K).

Нетрудно построить машинуТьюринга, преобразующую W (K) в W (K 0 ) за O(L3 ) шагов. КНФ K 0 , возможно, содержит скобки вида (y ∨ y) и (y ∨ ȳ), атакже скобки, отличающиеся лишь порядком слагаемых. Удаление этих вхождений можно осуществить за число шагов, непревосходящее O(L21 ), где L1 длина W (K 0 ), а, значит, не более чем за O(L4 ) шагов, где L — число букв в W (K).Поскольку число переходов не превосходит n − 1 ≤ 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 выполнима.Пусть C = y1 ∨ ... ∨ ym — скобка, являющаяся сомножителем КНФ K, и m > 3. Обозначим через K1 КНФ, полученнуюиз K вычеркиванием скобки C.

Пусть u — переменная, не входящая в K. Положим D = (y1 ∨ y2 ∨ u)(y3 ∨ ... ∨ ym ∨ ū).Покажем, что КНФ K выполнима тогда и только тогда, когда КНФ D&K1 выполнима.Пусть αe = (α1 , ..., αn ) — набор, обращающий КНФ K в единицу. Положим g(x1 , ..., xn ) = y1 ∨ y2 и h(x1 , ..., xn ) =y3 ∨ ... ∨ ym . Тогда g(eα) ∨ h(eα) = 1. Если g(eα) = 1, то набор βe = (α1 , ..., αn , 0) обращает КНФ D&K1 в единицу (последняякоордината набора βe есть значение переменной u).

Если g(eα) = 0, то набор βe = (α1 , ..., αn , 1) обращает КНФ D&K1 вединицу.Пусть теперь βe = (α1 , ..., αn , β) — набор, обращающий КНФ D&K1 в единицу. Пусть сначала β = 0. Тогда g(eα) = 1 иD&K1 (eα) = 1, а, значит, K(eα) = 1. Если же β = 1, то h(eα) = 1 и D&K1 (eα) = 1.Указанное выше преобразование КНФ K в КНФ D&K1 уменьшает на единицу число букв в скобке C и увеличиваетобщее число букв на 2.

Пусть m1 , ..., mk — числа букв в скобках КНФ K и mi > 3. Тогда достаточно добавить аналогичнымспособом не более 2(m1 + ... + mk − 3k) букв с тем, чтобы получить 3-КНФ K ∗ , выполнимую тогда и только тогда, когдаКНФ K выполнима.Полиномиальность преобразования очевидна.2Упражнение. Доказать N P -полноту задачи 4-ВЫП.Задача ТАВТОЛОГИЯ определяется следующим образом.ВХОД: ДНФ D = D(x1 , . . . , xn ).СВОЙСТВО: D(α1 , . . . , αn ) = 1 для всякого набора (α1 , .

. . , αn ).Упражнение. Доказать N P -полноту задачи ТАВТОЛОГИЯ.Список литературы[1] Кибернетический сборник (Нов. серия), No 12 , М.: МИР, 1975, С. 5–10.[2] А. Ахо, Д. Хопкрофт, Д. Ульман// Построение и анализ вычислительных алгоритмов, М.: Мир, 1979, 536 С.176 Некоторые N P -полные задачиВ этом параграфе расширяется список N P -полных задач. Доказывается N P -полнота задач 0-1 ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ, КЛИКА, ВЕРШИННОЕ ПОКРЫТИЕ, ПОКРЫТИЕ МНОЖЕСТВ, РАСКРАСКА. ДоказательствоN P -полноты очередной задачи проводится путем сведения к ней одной из уже известных N P -полных задач. Сведениесостоит в преобразовании входов некоторой задачи во вход исследуемой задачи с условием, что соответствующие свойстваодновременно выполняются или не выполняются для рассматриваемых задач. Принадлежность задач классу NP, как правило, является очевидной и не доказывается.

Полиномиальность преобразования входов также легко усматривается. Ниже(см. рис. 6.1) дана схема сведения задач.Рис. 6.1Задача 0-1 ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ (0-1 ЦЛП):ВХОД: Матрица A = (aij ) размера p × n и целочисленный вектор b = (b1 , ..., bp ).СВОЙСТВО: Cуществует 0-1-вектор x = (x1 , ..., xn ) такой, чтоAxT ≥ bT .(17)Теорема 6.1 ВЫП ≺ 0-1 ЦЛП.Доказательство.Пусть K = C1 &...&Cp — произвольная КНФ с p скобками, зависящая от переменных x1 , . . . , xn . Для i = 1, . . .

, p, j = 1, . . . , nположим 1, если xi ∈ Cj ,−1, если x̄i ∈ Cj ,aij =0, иначеиbi = 1− число отрицаний переменных в Ci .Очевидно, что вход задачи 0-1 ЦЛП можно задать словом длины, не превосходящей O(np), а преобразование записи КНФK в запись входа задачи 0-1 ЦЛП можно осуществить на детерминированной машине Тьюринга за полиномиальное времяот длины записи КНФ K.Покажем, что 0-1-вектор x = (x1 , ..., xn ), удовлетворяющий (17), существует тогда и только тогда, когда КНФ K выполнима.Достаточность.

Пусть K выполнима. Тогда существует набор α̃ = (α1 , ..., αn ) значений переменных такой, что K(α̃) = 1.Обозначим через Ai строку (ai1 , . . . , ain ) матрицы A. Покажем, что (17) выполнено при x = α̃. Для этого убедимся, что длявсякого i = 1, . . . , p выполнено(Ai , x) ≥ bi = 1 − число отрицаний переменных в Ci .(18)В самом деле, скобка Ci обращается на наборе α̃ в 1. Это означает, что либо существует переменная из Ci , обращающаясяв 1, либо в Ci существует отрицание некоторой переменной, обращающейся в 0. В первом случае минимальное значениескалярного произведения (Ai , x) достигается в случае, когда все координаты xj при коэффициентах aij , равных 1, заисключением одного, обращаются в 0, а все координаты xj при коэффициентах aij , равных −1, обращаются в 1. Во18втором случае минимальное значение скалярного произведения (Ai , x) достигается в случае, когда все координаты xj прикоэффициентах aij , равных 1, обращаются в 0, а все координаты xj при коэффициентах aij , равных -1, за исключениемодного, обращаются в 1.

В обоих случаях (18) удовлетворяется.Необходимость. Пусть существует двоичный вектор x = (x1 , ..., xn ), удовлетворяющий (17). Покажем, что K(x) = 1, азначит, КНФ K выполнима. Из (17) следует, что (18) выполнено для всякого i = 1, . . . , p. Отсюда вытекает, что все скобкиКНФ K содержат хотя бы одну букву, обращающуюся в 1 на наборе x = (x1 , ..., xn ).2Пример. Для КНФ K = (x1 ∨ x2 )&(x̄1 ∨ x̄2 ∨ x3 ) входом соответствующей задачи 0-1 ЦЛП являются матрица11 0A=−1 −1 1и вектор b = (1, −1). Решением неравенства (17) являются векторы (0, 1, α), (1, 0, β) и (1, 1, 1), где α, β ∈ {0, 1}.

Они жеобращают КНФ K в единицу.Задача КЛИКА:ВХОД: Граф G = (V, E), число k.СВОЙСТВО: В G существует полный подграф с k вершинами (k-клика).Теорема 6.2 ВЫП ≺ КЛИКА.Доказательство.Пусть КНФ K = C1 &...&Cq , зависящая от переменных x1 , . . . , xn , является конъюнкцией некоторых 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 , i > и < yj , j >, такие, что yi = ȳj , были смежны в графе G.

Еслиположить все переменные из S равными 1, а переменные из S̄ равными 0, то каждая скобка Ci обратится в 1. Значит, КНФK выполнима.2Пример. Для КНФ K = (x1 ∨ x2 )&(x̄1 ∨ x̄2 ∨ x3 ) входом соответствующей задачи КЛИКА являются граф G, показанныйна рис. 6.2, и число 2.19Рис. 6.2Задача ВЕРШИННОЕ ПОКРЫТИЕ:ВХОД: Граф 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. Поэтому всякое ребро из Ḡ инцидентно хотя бы одной вершине из V \ A. Аналогично, если V \ A является вершиннымпокрытием графа Ḡ, то каждое ребро из Ḡ инцидентно хотя бы одной вершине из V \A. Поэтому никакое ребро не соединяетдве вершины из A, а значит, A — клика в G.2Рис. 6.3Пример.

Граф G с множеством вершин {1, 2, 3, 4} (см. рис. 6.3 a) содержит клику {1, 2, 3}. В графе G (см. рис. 6.3 б)дополнение этого множества покрывает все ребра.Задача ПОКРЫТИЕ МНОЖЕСТВ:ВХОД: Семейство F = {S1 , . . . , Sm } подмножеств множества S такое, что ∪Sj ∈F = S, и число h.СВОЙСТВО: Cуществует подсемейство T ⊆ F такое, что |T | ≤ h и при этом ∪Sj ∈T = S.Теорема 6.4 ВЕРШИННОЕ ПОКРЫТИЕ ≺ ПОКРЫТИЕ МНОЖЕСТВ.Доказательство.Пусть задан вход задачи ВЕРШИННОЕ ПОКРЫТИЕ: граф G0 = (V 0 , E 0 ) и число l. ПоложимS = E 0 , Sj = {< u, vj >∈ E 0 : u ∈ V 0 } и h = l.Очевидно, подсемейство T = {Si1 , . .