Доказательство результатов об np-полноте.

Опираясь на Лемму 3, доказательство NP-полноты любой задачи П состоит из следующих четырёх шагов:

1. Доказательство того, что ПNP.

2. Отыскание некоторой задачи П’NPC из имеющегося обширного списка NP-полных задач.

3. Построение функции f, сводящей П’ к П.

4. Доказательство того, что функция f осуществляет полиномиальное сведение.

Шесть основных np-полных задач.

1. 3-ВЫПОЛНИМОСТЬ (3-ВЫП)

Условие: Дан набор дизъюнкций C={c₁, c₂, …, c_m} на конечном множестве переменных U, причём |c_i|=3 при .

Вопрос: Существует ли на U набор значений истинности, при котором выполняются все дизъюнкции из C?

2. ТРЁХМЕРНОЕ СОЧЕТАНИЕ (3-С)

Условие: Дано множество MXYZ, причём множества X, Y и Z и являются непересекающимися и имеют одинаковое число элементов q.

Вопрос: Верно ли, что M содержит 3-сочетание, т.е. некоторое подмножество M’M, такое, что |M’|=q и никакие два разных элемента M’ не имеют ни одной равной координаты?

3. ВЕРШИННОЕ ПОКРЫТИЕ (ВП)

Условие: Дан граф G=(V,E) и положительное целое число k, k|V|.

Вопрос: Имеется ли в графе G вершинное покрытие не более чем из k элементов, т.е. такое подмножество V’V, что |V’|  k и для каждого ребра {u, v}E хотя бы одна из вершин u или v принадлежит V’ ?

4. КЛИКА

Условие: Заданы граф G=(V,E) и положительное целое число J|V|.

Вопрос: Имеется ли в графе G клика мощностью не менее чем J, т.е. такое подмножество V’V, что |V’|J и любые две вершины из V’ соединены ребром из E?

5. ГАМИЛЬТОНОВ ЦИКЛ (ГЦ)

Условие: Дан граф G=(V, E).

Вопрос: Верно ли, что граф G=(V,E) содержит гамильтонов цикл.

6. РАЗБИЕНИЕ

Условие: Заданы конечное множество A и «вес» s(a) N каждого aA.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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