NP-полные и NP-трудные задачи
Начнем с определений.
Задача Z называется NP-трудной, если любая другая задача Z' NP полиномиально сводима к задаче Z.
Задача Z называется NP-полной, если Z есть NP-трудная задача и Z NP.
Получается, что NP-полные задачи – как бы самые сложные задачи в классе NP: если для одной (любой) из этих задач будет найден полиномиальный алгоритм решения, то тогда любую NP-задачу можно будет решить за полиномиальное время. Для этого ее следует свести к соответствующей NP-полной задаче (за полиномиальное время!) и решить NP-полную задачу (тоже за полиномиальное время). Иначе говоря, если одна какая-нибудь NP-полная задача принадлежит классу P, то тогда классы P и NP полностью совпадают. Таким образом, отыскание хотя бы одного полиномиального алгоритма для какой-нибудь NP-полной задачи стало бы эпохальным событием в истории информатики. Никому не возбраняется попробовать свои силы.
Насколько реально доказать для какой-нибудь конкретной задачи, что она является NP-полной или NP-трудной? Кажется безнадежным делом доказывать полиномиальную сводимость всех NP-задач к одной конкретной. Отметим однако, что дело облегчается, если каким-то образом доказана NP-полнота хотя бы одной задачи. Пусть имеется одна доказанно NP-полная задача Z1. Чтобы доказать NP-полноту задачи Z2, достаточно сделать две вещи: во-первых, показать, что Z2 NP (это обычно несложно), и во-вторых, суметь построить полиномиальное сведение Z1 Z2(а не Z2 Z1, обратите внимание на направление!) Тогда получается, что любая NP-задача Z полиномиально сводится к Z2через Z1. Теперь у нас есть уже две NP-полные задачи, Z1иZ2, и для следующей задачи Z3можно уже выбирать, что легче доказать: Z1 Z3или Z2 Z3. И так далее. В настоящее время известны сотни (если уже не тысячи) NP-полных и NP-трудных задач.
Отметим, что большая часть NP-полных задач – это задачи типа поиска («существует ли допустимый план?»). Для соответствующих задач оптимизации удается доказать NP-трудность, но далеко не всегда легко доказывается принадлежность классу NP.
Вообще, если Z – NP-полная задача, то для дополнительной задачи ~Z легко доказать NP-трудность, но мы видели выше, что принадлежность классу NP может и не иметь места.
Теорема Кука
Эта теорема (S.A.Cook, 1971г.) – тот самый первый шаг, о котором говорилось выше: доказательство NP-полноты одной конкретной задачи.
Как вообще можно доказать сводимость всех NP-задач к данной задаче? Можно воспользоваться определением NP-задачи: для нее имеется НМТ, принимающая индивидуальные задачи за полиномиальное время. А каждую НМТ можно описать, закодировав ее правила перехода. Тогда любую NP-задачу можно сформулировать следующим образом. Дано описание НМТ для данной массовой задачи Z и дано описание индивидуальной задачи z Z в виде записи с длиной l на ленте этой НМТ. Верно ли, что существует допустимое вычисление этой НМТ при этом исходном состоянии ленты, которое не более, чем за P(l) тактов приводит в состояние qy? Заметьте, что специфика конкретной задачи Z здесь исчезла, или вернее – она закодирована в правилах НМТ. Назовем такую «универсальную» NP-задачу Z0.
Теперь нам нужно сделать следующее. Нужно выбрать некоторую задачу распознавания Z1и предложить алгоритм, который за полиномиальное (относительно l) время будет переводить описание индивидуальной задачи z0 Z0в описание эквивалентной индивидуальной задачи z1 Z1. Тогда ясно, что задача Z1является NP-трудной, поскольку мы фактически умеем полиномиально сводить к ней любую NP-задачу.
Рассмотрим задачу о выполнимости КНФ.
Даны переменные X = {xi, i=1...N} и конъюнктивная нормальная форма (КНФ) G(X). Существует ли такой план X, для которого G(X) = 1?
Теорема Кука. Задача о выполнимости КНФ NP-полна.
Приведем эскиз доказательства (т.е. не будем добиваться полной строгости рассуждений, но покажем их общий ход).
Пусть n – число состояний НМТ, m – число букв ленточного алфавита, l – длина описания некоторой индивидуальной NP-задачи z Z на ленте НМТ, P(l) – полином из определения NP-задачи (т.е. это верхняя оценка числа тактов, за которые НМТ принимает любую индивидуальную задачу z Z, имеющую длину l и ответ «Да».) Введем три набора булевых переменных, которые в совокупности описывают функционирование заданной НМТ.
1) {Qik, 0iP(l), 0kn}; Qik = 1, если на такте i НМТ находится в состоянии k.
2) {Hij, 0iP(l), -P(l)jP(l)}; Hij = 1, если на такте i текущей ячейкой ленты является ячейка j.
3) {Aijr, 0iP(l), -P(l)jP(l), 0rm}; Aijr = 1, если на такте i в ячейке j записана буква ar.
Любой набор значений переменных Qik, Hij, Aijr описывает некоторое вычисление НМТ, т.е. одну ветвь дерева вычислений НМТ, включая ее начальное состояние и все переходы. Но не любой набор значений описывает корректное поведение машины, некоторые наборы могут описывать такую чушь, как одновременное пребывание в нескольких состояниях, несколько букв в одной ячейке, неправильные переходы и т.п. Чтобы выделить допустимые вычисления НМТ, следует наложить еще некоторые условия на значения переменных. Таковые условия можно объединить в 6 групп. Опишем их сначала словесно.
1. На любом такте работы НМТ находится ровно в одном состоянии.
2. На любом такте работы головка НМТ находится ровно в одной позиции ленты.
3. На любом такте работы каждая ячейка ленты содержит ровно одну букву ленточного алфавита.
4. На такте i = 0 НМТ находится в состоянии q0, головка на ячейке 1, на ленте записано описание решаемой индивидуальной задачи.
5. Не позднее, чем через P(l) тактов НМТ приходит в состояние qy (принимает задачу).
6. Все изменения конфигурации НМТ между тактами i и i+1 происходят в соответствии с правилами перехода данной НМТ.
Такое подробное изложение довольно очевидных вещей нужно для того, чтобы от словесных условий перейти к формально заданным.
Для формализации условий корректности вполне подходит аппарат КНФ. Выпишем соответствующие КНФ.
1. (Qi0 Qi1 ... Qin) & (~Qi0 ~Qi1) & (~Qi0 ~Qi2) & ...
& (~Qi,n-1 ~Qi,n), 0iP(l) (т.е. хотя бы одна Qijистинна, но не две одновременно!).
2. Аналогичная конструкция для переменных Hij.
3. Для Aijrтак же по смыслу, только индексов больше:
(Aij0 Aij1 ... Aijm) & (~Aij0 ~Aij1) & ... & (~Ai,j,m-1 ~Ai,j,m),
0iP(l), -P(l)jP(l).
4. Q00 & H01 & A0,1,v1 & A0,1,v2 & ... & A0,l,vl & A0,l+1,0.
Здесь av1, av2, ... avl - входное слово на ленте (описание решаемой задачи).
5. QP(l),1 (полагая, что принимающее состояние qy пронумеровано как q1).
6. Это условие следует разбить на два:
6.1. Если на такте i головка не находится в позиции j, то буква в этой ячейке не изменится при переходе к такту i+1.
~Aijr Hij Ai+1,j,r, 0iP(l), -P(l)jP(l), 0rm.
Эта дизъюнкция кажется несколько загадочной, однако заметим, что ее отрицание означало бы следующее: в ячейке j была буква ar, головки там не было, но буква изменилась! Ясно, что этого не может быть, поэтому записанная дизъюнкция истинна.
6.2. Если на такте i НМТ была в состоянии qk, головка находилась в позиции j и там была записана буква ar, то на такте i+1 НМТ должна оказаться в одной из тех конфигураций (q'k, j', a'r), которые получаются применением одного из правил перехода этой НМТ с подходящей левой частью:
~Qik ~Hij ~Aijr (Hi+1,j'Qi+1,k'Ai+1,j,r' Hi+1,j''Qi+1,k''Ai+1,j,r'' …)
Здесь 0iP(l), -P(l)jP(l), 0kn, 0rm.
Индексы с разным числом штрихов относятся к правым частям различных правил перехода с одной и той же левой частью. Выражение в скобках не находится в конъюнктивной нормальной форме. В ходе приведения этого выражения к КНФ его длина может сильно возрасти, однако можно показать, что длина выражения остается ограниченной некоторым полиномом от l.
Только в условии 6.2 фигурируют правила перехода конкретной НМТ.
Наконец, соединим все выписанные выражения из всех 6 групп с помощью операций конъюнкции. Результатом будет КНФ G(Q, H, A), зависящая как от рассматриваемой массовой задачи Z, так и от ее индивидуального представителя z.
Предположим, эта КНФ выполнима, т.е. существует набор Qik, Hij, Aijr, выполняющий все 6 условий. Но по смыслу условий это означает, что существует принимающее вычисление НМТ, т.е. исходная задача распознавания z Z имеет ответ «Да». И наоборот, если существует принимающее вычисление, то его ход можно закодировать набором переменных Qik, Hij, Aijr, которые по построению будут выполнять КНФ G(Q, H, A). Тем самым мы доказали эквивалентность задачи z и задачи о выполнимости КНФ G(Q, H, A). Таким образом, задача Z была сведена к задачи о выполнимости (сокращенно – задаче ВЫП). Было ли это сведение полиномиальным по времени относительно l? Да, ибо все сведение задачи заключалось просто в выписывании логических выражений, длина и количество которых ограничены полиномом от l.
Поскольку Z – произвольная задача из NP, то доказана полиномиальная сводимость любой NP-задачи к задаче ВЫП. В то же время задача ВЫП, очевидно, проверяема за полиномиальное время (на самом деле даже за линейное: для проверки нужно просто подставить значения переменных в КНФ и убедиться, что все элементарные дизъюнкции истинны), а потому эта задача принадлежит NP. Значит, задача ВЫП является NP-полной, что и требовалось доказать.
Примеры NP-полных задач
Задача «3-Выполнимость (задача 3-ВЫП)». Эта задача очень похожа на задачу ВЫП: дана КНФ от переменных x1, x2, ... xn, но при этом каждая элементарная дизъюнкция содержит ровно три члена. Требуется определить, существует ли набор значений переменных, при котором КНФ равна 1.
Очевидно, что данная задача принадлежит NP, т.к. она представляет собой частный случай задачи ВЫП. Чтобы доказать NP-полноту, следует показать, что задачу ВЫП можно полиномиально свести к 3-ВЫП.
Поскольку задача ВЫП более общая, чем 3-ВЫП, сведение ВЫП к 3-ВЫП потребует введения дополнительных переменных, чтобы «компенсировать качество количеством».
Вместо того, чтобы излагать доказательство в общем виде, рассмотрим конкретный пример, на котором хорошо видны идеи доказательства.
Пусть дана следующая КНФ от 8 переменных:
G(X) =x1& (x1x3) & (x2x4x6) & (x3x5 x7 x8)
& (x1x2 x3x4 x5 x8) .
Дизъюнкции G(X) имеют разную длину. Покажем, как можно преобразовать их в дизъюнкции длины 3, сохранив при этом свойство выполнимости (или невыполнимости) КНФ.
1) x1 (x1y1y2) & (x1y1 y2) & (x1 y1y2)
& (x1 y1 y2) .
Введены дополнительные переменные y1и y2, однако выражение в правой части тождественно равно x1, что нетрудно показать путем упрощения выражения.
2) x1x3 (x1x3y3) & (x1x3 y4) .
Аналогичный случай.
3) x2x4x6.
Не требует преобразования.
4) x3x5 x7x8 (x3x5y5) & (y5 x7x8) .
Если левая часть истинна, то истинен хотя бы один ее символ. Пусть это, например,x5. Поскольку при этом в правой части первая дизъюнкция уже истинна, положим y5=1, тогда и вторая дизъюнкция истинна. Если же левая часть ложна, то ложны все ее символы, а тогда в правой части при любом значении y5одна из дизъюнкций ложна.
5)x1x2 x3x4 x5 x8(x1x2y6) & (y6 x3y7) & (y7x4y8) & (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‑ВЫП. Как и раньше, вместо строгого доказательства покажем основные идеи на примере.
Пусть дана следующая КНФ: (x1x3x4) & (x1 x2x4). Число переменных 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. Можно ли так распределить задачи по процессорам, чтобы успеть к этому сроку?
Упрощенные шашки nn. Дана доска размером nn, дано расположение дамок (простых шашек нет). Есть ли у белых выигрыш в данной позиции?
Минимизация ДНФ. Задана булева функция F(X) от n переменных (например, в форме таблицы истинности или в виде совершенной ДНФ). Дано число K. Существует ли для этой функции ДНФ, состоящая не более, чем из K конъюнкций?