Основные NP-полные задачи. Сильная NP-полнота

В данном разделе устанавливается NP -полнота некоторых известных в различных приложениях задач. Предпочтение отдается графическим задачам как наиболее наглядным. Доказательство получается преобразованием в рассматриваемую задачу другой задачи, NP -полнота которой установлена. Для задач с целочисленными параметрами вводится важное понятие – сильная NP -полнота.

1. Пусть f (x ₁, …, x_n) — формула от булевых переменных x ₁, …, x_n в конъюнктивной нормальной форме, где каждая дизъюнкция имеет не более, чем три вхождения переменных. Задача проверки выполнимости таких формул называется задачей 3-выполнимости (идентификатор: 3ВЫП).

Утверждение 18.6. Задача 3ВЫП является NP -полной.

Доказательство. Достаточно доказать, что ВЫПµ3ВЫП. Пусть F = D ₁ D ₂ … D_m — индивидуальная задача выполнимость от переменных x ₁, …, x_n. Пусть D_i = z ₁ Ú z ₂ Ú … Ú z_k и k > 3, . Положим

где y ₁, …, y_{k -3} — новые переменные. Покажем, что:

D_i выполнено тогда и только тогда, когда существует значение y ₁, …, y_{k -3} такое, что выполнено;

D_i не выполнено тогда и только тогда, когда для любых значений y ₁, …, y_{k -3} не выполнено.

Действительно:

D_i = 0 Þ z ₁ Ú z ₂ Ú … Ú z_k = 0 Þ

;

D_i = 1 Þ z ₁ Ú z ₂ Ú … Ú z_k = 1 Þ .

Укажем значения переменных y ₁, …, y_{k -3}, выполняющие (табл.18.3).

Таблица 18.3

	y 1	y 2	y 3	…	yk -3
z 1 = 1				…
z 2 = 1				…
z 3 = 1				…
z 4 = 1				…
…	…	…	…	…	…
zk = 1				…

Проделаем теперь процедуру замены каждой дизъюнкции D_i на для каждого с условием k > 3. Получим задачу 3-выполнимости за полиномиальное время. По доказанному имеем ВЫПµ3ВЫП, что и требовалось доказать.

Замечание. Можно доказать, что задача 2-выполнимости лежит в классе P.

2. Рассмотрим графическую задачу (идентификатор: КЛИКА): по произвольному графу G (V, E) и числу k узнать, имеется ли в графе G полный (граф называется полным, если любые две вершины соединены ребром) подграф с k вершинами (клика).

Утверждение 18.7. Задача КЛИКА является NP -полной.

Доказательство. Ясно, что КЛИКА Î NP, так как словом-отгадкой для задачи служит список вершин, составляющих клику и детерминированный алгоритм за полиномиальное время проверяет наличие ребра между каждой парой вершин. Покажем, что ВЫП µ КЛИКА.

Пусть F = D ₁ D ₂… D_m — произвольная индивидуальная задача ВЫП. Строим соответствующий граф G_F следующим образом. Каждому вхождению переменной в F сопоставим вершину графа и присвоим ей обозначение (x ^a, i), где x ^a — вхождение переменного (a Î {0, 1}), i — номер соответствующей дизъюнкции. Вершины (x ^a, i) и (y ^b, j) соединим ребром в том и только в том случае, когда i ¹ j и x ^a не есть отрицание y ^b (т.е. x ¹ y или, если x = y, то a = b). Допустим, что F выполнима и пусть — соответствующий выполняющий набор. В каждом сомножителе F есть вхождение переменной, обратившее его в 1. Выберем по одному такому вхождению из каждой дизъюнкции. Рассмотрим соответствующее множество К вершин графа G_F и покажем, что любые две такие вершины соединены ребром. Действительно, для вершин (x ^a, i) и (y ^b, j) нет соединяющего ребра лишь в случае i = j, либо . Но x ¹ y, так как вхождения переменных взяты из разных дизъюнкций. Если , то одно и то же значение переменного х не может одновременно обратить в 1 x ^a и y ^b. Значит, из выполнимости F следует наличие клики размера k в G_F.

Обратно, пусть G_F содержит клику размера k. Пусть это набор вершин . Покажем, что формула F выполнима. Положим , и тогда . Значения остальных переменных положим произвольно. Противоречия в выборе значений переменных нет, так как если и соединены ребром, то a = b.

По построению G_F вершинам соответствуют вхождения переменных из разных дизъюнкций и так как число вершин равно k, то каждая дизъюнкция имеет вхождение переменного, обращающего в 1 при данных значениях переменных, значит и F обращается в 1. Построение G_F проводится за полиномиальное время и, следовательно, ВЫП µ КЛИКА, что и требовалось доказать.

3. Говорят, что некоторое множество вершин графа G (V, E) образует вершинное покрытие графа, если для любого ребра e Î E найдется инцидентная ему вершина v Î V ₁ этого множества. Задача о вершинном покрытии (идентификатор: ВП) состоит в том, чтобы по произвольному графу G (V, E) и числу К узнать, имеет ли граф вершинное покрытие мощности k.

Утверждение 18.8. Задача ВП является NP -полной.

Доказательство. Ясно, что ВПÎ NP, так как словом-догадкой является список вершин соответствующего вершинного покрытия и правильность ответа проверяется за полиномиальное время. Покажем, что КЛИКА µ ВП.

Для графа G (V, E) строим граф G ’, являющийся дополнением G до полного графа (т.е. G ’ = (V, E’)), где e Î E’ Û e Ï E). Покажем, что А есть полный подграф в G Û дополнение А ’ = V \ A есть ВП в G ’.

Действительно, пусть полный подграф с множеством вершин А лежит в G. Тогда, если бы для ребра графа G ’ выполнялось бы и , то должно быть, что ребра нет в G. Значит А ’ = V \ A — вершинное покрытие для G ’.

Обратно, если А ’ образует вершинное покрытие графа G ’, то всякое ребро, оба конца которого находятся в А, не может принадлежать G ’ и содержится в G, т.е. в G имеется полный подграф с множеством вершин А.

Итак, задача о к -вершинном полном подграфе сводится к задаче о вершинном покрытии мощности k ’ = n – k, n = | V |. Доказательство закончено.

Говорят, что множество вершин графа G (V, E) независимо, если никакие две вершины из V ₁ не связяны ребром. Задача о независимом множестве вершин (идентификатор: НВ) заключается в том, чтобы для произвольного графа G (V, E) и целого числа k выяснить, существует ли в G независимое множество из к вершин.

Утверждение 18.9. Задача НВ является NP -полной.

Доказательство аналогично предыдущему.

Приведем теперь без доказательства некоторые известные NP -полные проблемы. За доказательствами можно обратиться к книге: Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М., 1983.

5. Задача ГАМИЛЬТОНОВ ЦИКЛ (идентификатор: ГЦ).

Для произвольного графа G (V, E) требуется узнать, существует ли перестановка вершин такая, что выполнено:

6. Задача ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК (идентификатор: ЦР).

Для произвольных натуральных чисел и k требуется узнать, существует ли набор целых чисел , что выполнено . Вариантом данной задачи является (0,1)-рюкзак, в которой требуется установить существование (0,1)-чисел с условием .

7. Множество ребер, разрезающих циклы. Для произвольного графа G (V, E) и целого числа к выяснить, существует ли множество , такое, что и каждый цикл графа G (V, E) содержит ребро из .

8. Множество вершин, разрезающих циклы. То же, но только теперь ищется подмножество множества вершин.

9. Изоморфизм подграфу. Для заданных двух графов G (V ₁, E ₁) и H (V ₂, E ₂) выяснить, содержит ли граф G (V, E) подграф, изоморфный Н.

10. Проблема разрешимости диофантовых уравнений (в стандартном двоичном кодировании данных) вида

.

В настоящее время известно большое число NP -полных задач из разных областей дискретной математики (несколько тысяч). Мы ограничимся приведением результата, полученного Шеффером Т.И. (1978), дающего бесконечную серию NP -полных проблем.

Пусть — любое конечное множество логических отношений. Логическое отношение определяется как некоторое подмножество из {0, 1} ^k для некоторого целого k ³ 1, при этом k называется рангом отношения. Определим S -формулу как произвольную конъюнкцию скобок, каждая вида , где — переменные, число которых соответствует рангу . Проблема S -выполнимости — это проблема разрешения, является ли данная S -формула выполнимой.

Например, пусть R (x, y, z) — 3-местное логическое отношение с таблицей истинности {(1, 0, 0), (0, 1, 0), (0, 0, 1)}. Тогда формула R (x, y, z) × R (x, y, u) × R (u, u, y) выполнима и (x, y, z, u) = (0, 1, 0, 0) — ее выполняющий набор.

Результат Шеффера состоит в том, что проблема S -выпол­нимости полиномиально разрешима, если множество S удовлетворяет по крайней мере одному из приводимых ниже условий (в противном случае проблема NP -полна):

1) каждое отношение из S 0-выполнимо, т.е. (0, …, 0) ;

2) каждое отношение из S 1-выполнимо, т.е. (1, …, 1) ;

3) каждое отношение из S слабо положительно, т.е. логически эквивалентно формуле КНФ, имеющей самое большее одно переменное с отрицанием в каждой дизъюнкции;

4) каждое отношение из S слабо отрицательно, т.е. логически эквивалентно формуле КНФ, имеющей самое большее одно переменное без отрицания в каждой дизъюнкции;

5) Каждое отношение из S мультиафинно, т.е. логически эквивалентно формуле, являющейся конъюнкцией линейных форм над полем GF (2);

6) каждое отношение из S биюнктивно, т.е. логически эквивалентно формуле КНФ, имеющей самое большее вхождения двух переменных в каждой конъюнкции.

Установим теперь NP -трудность некоторых задач, уже встречавшихся в курсе математической логики. Рассмотрим следующие задачи о булевых функциях.

Задача 1. РАВНОВЕРОЯТНОСТЬ БУЛЕВОЙ ФУНКЦИИ. Для данной булевой функции , заданной в КНФ, узнать, является ли она равновероятной (т.е. верно ли, что ее вес равен ).

Задача 2. ЛИНЕЙНОСТЬ БУЛЕВОЙ ФУНКЦИИ. Для данной булевой функции , заданной в КНФ, узнать, является ли она линейной.

Задача 3. СУЩЕСТВЕННОСТЬ ПЕРЕМЕННОГО. Для данных булевой функции в КНФ и целого числа к узнать, является ли переменное x_k существенным для f.

Задача 4. ФУНКЦИОНАЛЬНАЯ ПОЛНОТА. Для данной булевой функции в КНФ выяснить, образует ли f функционально полную систему (является ли f шефферовой).

Утверждение 18.10. Задачи (1 – 4) являются NP -трудными.

Доказательство.

Задача 1. Пусть — произвольная индивидуальная задача ВЫП, где = D ₁… D_m, D_i — дизъюнкции. Определим функцию = D ₁… D_m Ú y, где y — новое переменное. Имеем и, значит, КНФ для функции f * строится по функции f за полиномиальное время. Легко видеть, что . Значит, f * равновероятна тогда и только тогда, когда f не выполнима. Ясно, что условие «задача 1 Î P» влечет за собой ВЫП Î P, что означает задача 1 Î NPH.

Задача 2. Пусть — произвольная индивидуальная задача ВЫП. Определим функцию

,

где y ₁, y ₂ — новые переменные. Ясно, что КНФ для функции f * строится по f за полиномиальное время. Легко видеть, что f * линейна тогда и только тогда, когда f не выполнима и условие «задача 2 Î P» влечет за собой ВЫП Î P, что означает задача 2 Î NPH.

Задача 3. Пусть — произвольная индивидуальная задача ВЫП. Образуем функцию , где y — новое переменное. Ясно, что y существенно для f * тогда и только тогда, когда f — выполнима. Следовательно, «задача 3 Î P» влечет за собой ВЫП Î P, что означает задача 3 Î NP.

Задача 4. Пусть — произвольная индивидуальная задача ВЫП. Образуем функцию

.

Ясно, что КНФ для f * строится по f за полиномиальное время. Функция f * образует функционально полную систему тогда и только тогда, когда f выполнима. Действительно, если f не выполнима, то и f * не является функционально полной. Если f выполнима, то пусть - выполняющий набор. Тогда имеем

,

,

откуда следует не самодвойственность и не линейность функции f *. Очевидно, что f * не сохраняет нуль, не сохраняет единицу и не монотонна. Значит, функция f * удовлетворяет критерию Шеффера функциональной полноты. Следовательно, условие «задача 4 Î P» влечет за собой ВЫП Î P, что означает задача 4 Î NPН, что и требовалось доказать.

Замечание. Легко убедиться, что отрицание задачи 2, задачи 3 лежат в классе NP, и поэтому они NP -полны. Неизвестно, верно ли это для задач 1 и 4. Очевидно, что при табличном задании булевых функций рассмотренные задачи имеют полиномиальную сложность.

Разберем еще одно важное понятие, относящееся к обсуждаемому кругу вопросов. Рассмотрим задачу ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК, которая, как отмечалось выше, является NP -полной. Пусть c ₁, …, c_n, w — натуральные числа и спрашивается, существуют ли такие целые x ₁, …, x_n ³ 0, что выполнено . Приведем один алгоритм решения данной задачи. Для индивидуальной задачи ЦР(c ₁, …, c_n, w) построим ориентированный граф G (c ₁, …, c_n, w) = (V, E), где V = {0, 1, …, w }, E = {(m, k), 0 £ m < k £ £ w и k – m = c_j для некоторого j £ n }. Значит, граф G имеет w + 1 вершину и O(nw) дуг.

Утверждение 18.11. В графе G (c ₁, …, c_n, w) имеется путь из 0 в w тогда и только тогда, когда индивидуальная задача ЦР(c ₁, …, c_n, w) имеет решение.

Доказательство. Пусть (0 = i ₀, i ₁, …, i_m = w) — нужный путь в графе G. Рассмотрим набор чисел (s ₁, …, s_m) = (i ₁ – i ₀, …, i_m – i_{m -1}). Все эти числа содержатся среди чисел { c ₁, …, c_n } согласно определению графа G. Кроме того, имеем . Отсюда следует, что уравнение разрешимо в неотрицательных целых числах, причем x_j равно числу появлений c_j в последовательности (s ₁, …, s_m).

Обратно, если для неотрицательных целых чисел x ₁, …, x_n, то можно восстановить некоторый путь из 0 в w в графе G, если положить (s ₁, …, s_m) = () и путь из 0 в w имеет вид (0 = i ₀, i ₁, …, i_m = w), где i ₁ = s ₁, i ₂ = s ₁ + s ₂, …, i_m = s ₁ + … + s_m. Доказательство завершено.

Утверждение 18.12. Любая индивидуальная задача ЦР может быть решена за О (nw) действий.

Доказательство. По данным c ₁, …, c_n, w строим граф G за О (nw) действий. Затем за О (nw) действий проверяем существует ли путь из 0 в w, используя способ пометок: вершину 0 помечаем 0, вершины, достижимые из 0 за 1 шаг, помечаем 1 и т.д. Если w получает пометку, то задача разрешима, если нет, то неразрешима. Доказательство завершено.

Приведенный результат показывает, что NP -полная задача ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК решается с помощью алгоритма с временной сложностью О (nw) — полиномиального и, следовательно, доказано, что P = NP и можно считать ненужным предыдущее и последующее обсуждение теории NP -полноты. Дело в том, что оценка О (nw) не является полиномиальной функцией от длины входа, так как целые числа в экономном кодировании должны задаваться в двоичной системе счисления. В то же время приведенный результат важен, так как он показывает, что NP -полные задачи имеют разную «сложность».

Для задач с числовыми параметрами введем следующие определения. Пусть I — индивидуальная вычислительная задача, т.е. с числовыми параметрами. Обозначим через num (I) — наибольшее целое число, появляющееся в I.

Определение 18.13. Пусть А — вычислительная задача и f: N à N — числовая функция. Обозначим через A_f подзадачу задачи А, в которой берутся индивидуальные задачи I, для которых выполнено num (I) £ f (| I |). Говорят, что задача А сильно NP - полна, если для некоторого полинома p (n) задача A_p является NP -полной.

Замечание. Можно показать, что задачи КЛИКА, ГАМИЛЬТОНОВ ЦИКЛ являются сильно NP -полными, а задачи (0,1)-РЮКЗАК и ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК не являются таковыми.

Определение 18.14. Алгоритм АЛГ для задачи А называют псевдополиномиальным, если он решает любую индивидуальную задачу I Î A за время, ограниченное полиномом (двух переменных) от | I | и num (I). Значит, алгоритм со сложностью О (nw) для задачи ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК является псевдополиномиальным (ясно, что для индивидуальной задачи I ЦР num (I) = w).

Отметим, что сильная NP -полнота задачи делает маловероятным существование псевдополиномиального алгоритма точно также, как NP -полнота задачи делает маловероятным существование полиномиального алгоритма.

Утверждение 18.15. Если P ¹ NP, то ни для одной сильно NP -полной задачи не существует псевдополиномиального алгоритма.

Доказательство. Пусть А — сильно NP -полная задача. Значит, для некоторого полинома p (n) задача А_p является NP -полной. Далее, пусть для А существует псевдополиномиальный алгоритм АЛГ, который решает любую индивидуальную задачу I Î A за время q (| I |, num (I)) для некоторого полинома q от двух переменных. Тогда очевидно, что алгоритм АЛГ решает NP -полную задачу А_p за время q (n, p (n)) — что является полиномиальной оценкой. Получено противоречие при P ¹ NP, что и требовалось доказать.

Список Литературы

1. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

2. Ван дер Варден Б.Л. Алгебра. М.:Наука, 1976.

3. Верещагин Н.К., Шень А. Начала теории множеств. М.: МЦНМО, 1999.

4. Верещагин Н.К., Шень А. Вычислимые функции. М.: МЦНМО, 1999.

5. Верещагин Н.К., Шень А. Языки и исчисления. М.: МЦНМО, 2000.

6. Глухов М.М. Математическая логика. М., 1981.

7. Курош А.Г. Лекции по общей алгебре. М.: ГИФМЛ, 1962.

8. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физико-математическая литература, 1995.

9. Ленг С. Алгебра. М.: Мир, 1965.

10. Мальцев А.И. Алгебраические системы. М.: Наука, 1970.

11. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1986.

12. Марков А.А., Нагорный Н.М. Теория алгорифмов. М.: Наука, 1984.

13. Новиков П.С. Элементы математической логики. М.: Наука, 1973.

14. Носов В.А. Теория алгоритмов. М., 1990.

15. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.

[1] Дальше вместо ┐(А) будем писать ().

[2] Диофантовыми уравнениями называются алгебраические уравнения или системы алгебраических уравнений с рациональными коэффициентами, решения которых отыскиваются в целых или рациональных числах. Например,.

[3] Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. М., 1987. С.230.

[4] Часто программу для машины Тьюринга организовывают в виде таблицы.

[5] Частичная функция определена, вообще говоря, не для всех значений аргумента. В строгом смысле частичное отображение является произвольным подмножеством. Частичная функция — это однозначное частичное отображение.

[6] Мальцев А.И. Алгоритмы и рекурсивные функции. М., 1965. С.105.

[7] Марков А.А., Нагорный Н.М. Теория алгорифмов. М., 1984.

[8] Полностью доказательство приведено в 5-й главе книги Э. Мендельсона «Введение в математическую логику» (М., 1971).

[9] С результатами взаимного моделирования вычислительных моделей можно ознакомиться в работах: Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., 1979; Трахтенброт Б.А. Сложность алгоритмов и вычислений: спецкурс для студентов НГУ. Новосибирск, 1967.

Дата добавления: 2014-12-29