2.6. Примеры np-полных задач
Задача «3-Выполнимость (задача 3-ВЫП)». Эта задача очень похожа на задачу ВЫП: дана КНФ от переменных x1, x2, ... xn, но при этом каждая элементарная дизъюнкция содержит ровно три члена. Требуется определить, существует ли набор значений переменных, при котором КНФ равна 1.
Очевидно, что данная задача принадлежит NP, т.к. она представляет собой частный случай задачи ВЫП. Чтобы доказать NP-полноту, следует показать, что задачу ВЫП можно полиномиально свести к 3-ВЫП.
Поскольку задача ВЫП более общая, чем 3-ВЫП, сведение ВЫП к 3-ВЫП потребует введения дополнительных переменных, чтобы «компенсировать качество количеством».
Вместо того, чтобы излагать доказательство в общем виде, рассмотрим конкретный пример, на котором хорошо видны идеи доказательства.
Пусть дана следующая КНФ от 8 переменных:
G(X) =`x1 & (x1 Ú`x3) & (x2 Ú`x4 Ú`x6) & (x3 Ú`x5 Ú x7 Ú`x8) & (x1 Ú`x2 Ú x3 Ú`x4 Ú x5 Ú x8) .
Дизъюнкции G(X) имеют разную длину. Покажем, как можно преобразовать их в дизъюнкции длины 3, сохранив при этом свойство выполнимости (или невыполнимости) КНФ.
1) x1 Þ (`x1 Ú`y1 Ú`y2) & (`x1 Ú`y1 Ú y2) & (`x1 Ú y1 Ú`y2) & (`x1 Ú y1 Ú y2) .
Введены дополнительные переменные y1 и y2, однако выражение в правой части тождественно равно x1, что нетрудно показать путем упрощения выражения.
2) x1 Ú`x3 Þ (x1 Ú`x3 Ú`y3) & (x1 Ú`x3 Ú y4) .
Аналогичный случай.
3) x2 Ú`x4 Ú`x6 .
Не требует преобразования.
4) x3 Ú`x5 Ú x7 Ú`x8 Þ (x3 Ú`x5 Ú`y5) & (y5 Ú x7 Ú`x8) .
Если левая часть истинна, то истинен хотя бы один ее символ. Пусть это, например,`x5 . Поскольку при этом в правой части первая дизъюнкция уже истинна, положим y5=1, тогда и вторая дизъюнкция истинна. Если же левая часть ложна, то ложны все ее символы, а тогда в правой части при любом значении y5 одна из дизъюнкций ложна.
5) x1 Ú`x2 Ú x3 Ú`x4 Ú x5 Ú x8 Þ(x1 Ú`x2 Ú`y6) & (y6 Ú x3 Ú`y7) & (y7 Ú`x4 Ú`y8) & (y8 Ú x5 Ú x8) .
Случай, аналогичный предыдущему. Если в левой части хотя бы один символ истинен, то можно подобрать набор значений y6, y7, y8, при котором правая часть также истинна. Если левая часть ложна, то правая ложна при любых наборах y6, y7, y8.
Отметим более четко: в случаях 4 и 5 вовсе не утверждается, что левая часть тождественно равна правой. Дело в другом: если левая часть истинна, и только в этом случае, можно подобрать такие yi, что правая часть будет истинна.
Таким образом, если исходная КНФ выполнима, то можно дополнить выполняющий набор xi, подобрав такие yj, при которых выполнима и преобразованная КНФ. Наоборот, если при любых наборах xi остается хотя бы одна ложная дизъюнкция, то при любом наборе yj эта дизъюнкция останется ложной.
Нам удалось свести задачу ВЫП к задаче 3-ВЫП. По-хорошему, следует еще доказать, что такое сведение может быть выполнено за время, ограниченное полиномом от размера задачи. Для простоты изложения ограничимся тем же рассуждением, что при доказательстве теоремы Кука: если удлинение КНФ не очень велико, а процедура преобразования дизъюнкций очень проста, то отчего бы времени быть сверхполиномиальным?
Будем считать, что нам удалось таким образом доказать NP-полноту задачи 3‑ВЫП.
Задача о вершинном покрытии графа (задача ВП). Дан неориентированный граф G = (V, E) с множеством вершин V и множеством ребер E. Дано натуральное число K. Вершинным покрытием графа называется подмножество вершин V¢ Í V, такое, что любое ребро графа инцидентно хотя бы одной вершине из V¢. Требуется определить, существует ли вершинное покрытие графа G мощности £ K.
Для доказательства NP-полноты задачи ВП покажем, что к ней сводится задача 3‑ВЫП. Как и раньше, вместо строгого доказательства покажем основные идеи на примере.
Пусть дана следующая КНФ: (x1 Ú`x3 Ú`x4) & (`x1 Ú x2 Ú`x4). Число переменных n=4, число дизъюнкций m=2. Построим граф G по следующим правилам:
1. Для каждой переменной xi построим подграф из двух вершин, соединенных ребром. Пометим вершины символами xi и`xi.
2. Для каждой дизъюнкции ak построим подграф-треугольник, пометив его вершины символами ak1, ak2 и ak3.
3. Соединим каждую вершину каждого треугольника с вершиной, помеченной соответствующей переменной. Например, поскольку вторым символом первой дизъюнкции является `x3, следует соединить ребром вершины a12 и `x3. Эту группу ребер будем называть соединяющими ребрами.
Результат построения показан на рис.2.1.
Рис.2.1
Выберем значение K = n+2m = 8.
Докажем теперь, что в построенном графе G имеется вершинное покрытие V¢ мощности не более K в том и только том случае, если для исходной КНФ имеется выполняющий набор значений переменных.
Рассмотрим сначала, как может выглядеть вершинное покрытие для данного графа. Очевидно, в него должна входить по меньшей мере одна вершина из каждого подграфа xi -`xi, чтобы покрыть ребро этого подграфа. Из каждого треугольного подграфа ak в покрытие должны войти по крайней мере две вершины. Итого получается не менее n+2m = K вершин. Но при этом по условию задачи ВП покрытие должно содержать не более K вершин. Таким образом, покрытие должно содержать ровно K вершин, по одной из каждого подграфа xi -`xi и по две из подграфов ak .
Предположим, такое покрытие существует. При этом должны быть покрыты также все соединяющие ребра. Для каждого ak два таких ребра покрыты двумя вершинами ak, вошедшими в покрытие. Третье же соединяющее ребро должно быть покрыто вершиной из пары xi -`xi. Выпишем набор значений всех xi, соответствующий вершинам, вошедшим в покрытие. По построению графа очевидно, что при этих значениях переменных в каждую дизъюнкцию будет входить, по крайней мере, один истинный символ, т.е. КНФ будет выполнена.
Наоборот, пусть существует набор значений xi, обращающий в истину все дизъюнкции из КНФ. Включим в покрытие n вершин, помеченных символами этого набора. При этом, поскольку в каждой дизъюнкции присутствует хотя бы один символ из выполняющего набора, для каждого подграфа ak будет покрыто хотя бы одно соединяющее ребро. Включим в покрытие те две вершины ak, которые неинцидентны этому ребру (не лежат на нем). Выполним это для всех ak. При этом окажутся покрыты оставшиеся соединяющие ребра и все ребра подграфов ak, т.е. будет полностью построено вершинное покрытие из K вершин.
Эквивалентность задачи ВП и задачи 3-ВЫП доказана. Полиномиальность сведения не вызывает сомнений. Полиномиальная проверяемость задачи ВП тоже очевидна. Значит, задача ВП является NP-полной.
Еще несколько примеров NP-полных задач приведем без доказательства. Некоторые из них ранее уже упоминались. Все задачи формулируются здесь как задачи распознавания.
Задача о гамильтоновом цикле. Дан граф G = (V, E). Существует ли цикл, ровно один раз проходящий через каждую вершину?
В случае ориентированного графа можно поставить задачу об ориентированном гамильтоновом цикле. Она также NP-полна.
Задача о коммивояжере. Дано число n, матрица расстояний {aij, 1 £ i, j £ n} и число K. Существует ли маршрут коммивояжера (т.е. гамильтонов цикл) с длиной, не превышающей K? (К этой задаче легко сводится задача о гамильтоновом цикле).
Задача о самом длинном пути. Дан граф G = (V, E), заданы номера двух вершин A и B, а также число K. Существует ли путь из A в B с длиной не менее K?
Интересно, что для аналогичной задачи о самом коротком пути имеются хорошие полиномиальные алгоритмы.
Задача о разбиении. Даны n предметов с весами pi. Можно ли разбить множество предметов на два непересекающихся подмножества с одинаковым весом?
Эту задачу можно свести к задаче о рюкзаке.
Задача о рюкзаке. Имеется n наименований товара, заданы объемы единиц каждого товара bi и их стоимость ci, i = 1…n. Имеется рюкзак объема B. Можно ли подобрать набор товаров, вмещающийся в рюкзак и имеющий при этом стоимость не менее заданного значения K?.
Задача о конвейерном расписании. Даны m станков и n деталей, каждая из которых должна пройти обработку сначала на станке 1, затем на станке 2 и т.д. Время обработки i-той детали на j-том станке равно tij. Если станок занят, деталь ожидает его освобождения. Требуемый срок окончания обработки всех деталей равен K. Можно ли так выбрать порядок запуска деталей на обработку, чтобы успеть к этому сроку?
Следует подчеркнуть, что в этой задаче можно и нужно переставлять друг с другом детали, но нельзя изменять порядок станков.
При m = 2 это задача о двух станках, для которой известен очень простой алгоритм точного решения (попробуйте придумать его самостоятельно). При m = 3 получается задача о трех станках, которая уже NP-полна и очень трудна для решения.
Задача о многопроцессорном расписании. Даны m одинаковых процессоров, n независимых задач, время решения каждой задачи ti и требуемый срок окончания K. Можно ли так распределить задачи по процессорам, чтобы успеть к этому сроку?
Упрощенные шашки n´n. Дана доска размером n´n, дано расположение дамок (простых шашек нет). Есть ли у белых выигрыш в данной позиции?
Минимизация ДНФ. Задана булева функция F(X) от n переменных (например, в форме таблицы истинности или в виде совершенной ДНФ). Дано число K. Существует ли для этой функции ДНФ, состоящая не более, чем из K конъюнкций?