Некоторые методы доказательства np-полноты.

Имеется несколько общих приёмов из большого количества подходов доказательства NP-полноты, которые широко используются. Эти приёмы:

а) Сужение задачи

б) Локальная замена

в) Построение компонент

В лекциях, для краткости, мы будем опускать первый этап доказательства, показывающий принадлежность задачи к классуNP. Кроме того, чаще всего мы не будем показывать полиномиальность преобразования, когда оно достаточно очевидно.

Сужение задачи.

Данный метод является самым простым и широко используемым. Если мы доказываем, что некоторая задача ПNPявляетсяNP-полной, то здесь пытаемся установить, чтоПявляется более общим случаем некоторой известнойNP-полной задачиП’. Сущность метода заключается в том, чтобы указать дополнительное ограничение, которое требуется наложить на индивидуальные задачи изП, чтобы получилась в результате этого сужения задача изП’. При этом не требуется, чтобы возникающая новая задача была точной копией известнойNP-полной задачи. Таким образом, метод сужения можно рассматривать просто как иной взгляд на задачу, а не стандартный способ доказательства.

ПРИМЕРЫ доказательства методом сужения.

Рассмотрим задачу ТОЧНОЕ ПОКРЫТИЕ 3-МНОЖЕСТВАМИ (ТП-3).

Условие:Задано конечное множествоX, такое, что|X|=3q, и семейство Cтрёх элементных подмножеств множестваX.

Вопрос:Верно ли, что семействоCсодержитточное покрытиемножестваX, т.е. подсемействоC’C, что каждый элемент изXсодержится ровно в одном элементе изC.

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

Заметим, что любую индивидуальную задачу 3-С можно рассматривать как индивидуальную задачу из ТП-3, просто считая, что Mсостоит из неупорядоченных троек элементов множестваXYZ. При этом 3-сочетания для индивидуальной задачи из 3-С взаимно однозначно соответствуют точным покрытиям соответствующей индивидуальной задачи из ТП-3. Т.о. задача 3-С есть ограниченная версия задачи ТП-3, что доказываетNP-полноту задачи ТП-3.

Задача РЮКЗАК.

Условие:Задано конечное множествоU, веса элементовs(u)N, стоимости элементовv(u)N, общие ограничениеBNна размеры, стоимостьkN.

Вопрос:Существует ли подмножествоUU’, такое, что .

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

Если ограничится рассмотрением только таких задач, в которых для всех uUs(u)=v(u) и , то мы придём к задаче РАЗБИЕНИЕ, которая являетсяNP-полной, что доказываетNP-полноту.

Заметим, что описанный метод хорошо работает тогда, когда имеется обширный список известных NP-полных задач. Многие возникающие на практике задачи представляют собой часто усложнённые задачи из списка имеющихсяNP-полных задач.

Локальная замена.

Этот метод состоит в том, что выбирается некоторое характерное свойство известной NP-полной задачи, с помощью него образуется семействоосновных модулей, а соответствующие индивидуальные задачи исследуемой задачи получаются путём единообразной замены каждого основного модуля некоторой другой структурой. Важным моментом является то, что каждая замена приводит только к локальному изменению структуры, причём замены не зависят друг от друга.

Задача РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ.

Условие:Задан графG=(V,E)число вершин которого кратно 3, т.е. |V|=3q.

Вопрос: Существует ли такое разбиениеV наqнепересекающихся подмножествV₁,V₂, …, V_q, каждое из которых содержит ровно 3 элемента, и для каждогоV_i={v_i1, v_i2, v_i3} рёбра {v_i1, v_i2}, {v_i2, v_i3}, {v_i3, v_i1} принадлежатE.

Сведём задачу ТП-3 к задаче РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ.

Пусть множество X(|X|=3q) и семействоCего трёхэлементных подмножеств образуют условие произвольной индивидуальной задачи из ТП-3. Построим графG=(V,E), такой, что|V|=3qи для него существует искомое разбиение тогда и только тогда, когда семействоCсодержит точное покрытие множества.

Основными модулями рассматриваемой индивидуальной задачи из ТП-3 будут три трёхэлементные подмножества изC. Операция локальной замены превращает каждое элементарное подмножествоC_i=(x_i, y_i, z_i)C в наборE_i, состоящий из 18 рёбер. Это преобразование можно изобразить следующим образом:

Таким образом, формируемый граф Gбудет таким:

Заметим, что по построению только вершины из множества X могут быть инцидентны более чем одному множествуE_i. Кроме того, количество вершин|V|=3q+9|С|=3q’, где С– семейство трёхэлементных подмножеств.

Индивидуальную задачу РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ можно построить за полиномиальное время из задачи ТП-3. Если c₁, c₂, …, c_q– трёхэлементные подмножества изC, которые образуют ТП-3, то соответствующее разбиениеVна треугольникиV₁, V₂, …, V_q, строится следующим образом. Еслиc_i=(x_i, y_i, z_i)– элемент точного покрытия, то из множестваE_i выбираются элементы:(x_i, a_i[1], a_i[2]) (y_i, a_i[4], a_i[5]) (z_i, a_i[7], a_i[8])(a_i[3], a_i[6], a_i[9]).Если же элементc_i=x_i, y_i, z_iне входит в точное покрытие, то из множестваE_iвыбираются тройки(a_i[1], a_i[2], a_i[3]) (a_i[4], a_i[5], a_i[6]) (a_i[7], a_i[8], a_i[9]).Такой выбор элементов обеспечивает, что каждый элемент из множестваVсодержится ровно в одном трёхвершинном подмножестве рассматриваемого разбиения.

Обратно, если V=V₁V₂V₃ … V_q’– произвольное разбиение графаGна треугольники, то соответствующее точное покрытие множестваXполучается, если выбирать те подмножестваc_i, для которых (a_i[3], a_i[6], a_i[9])=V_jпри некоторомj, 1 ≤j≤q’.