19. Методы док-ва np-полноты. Метод сужения. Некоторые методы доказательства np-полноты.

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

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

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

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

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

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

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

МНОЖ ВЕРШ., РАЗ. КОНТ.

20. Методы доказательства 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]). Такой выбор элементов обеспечивает то, что каждый элемент из множества X содержится ровно в одном трёхвершинном подмножестве рассматриваемого разбиения.

Обратно, если 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’.

Приведённый пример представляет собой доказательство метода локальной замены в “чистом виде”. Здесь структура рассматриваемой индивидуальной задачи однозначно определялась структурой исходной задачи (NP-полнота которой известна).

Часто оказывается полезным дополнить рассматриваемую индивидуальную задачу вспомогательными элементами, которые играют роль ограничителя, налагающего дополнительные ограничения на способы получения ответа “да”.