18. Теорема Кука. 6 основных np-полных задач.

Наличие класса NP-полных задач доказывает теорема Кука.

Первой NP-полной задачей была задача распознавания из булевой логики, которая называется ВЫПОЛНИМОСТЬ:

Пусть U={u₁, u₂, …, u_m} – множество булевых переменных. Под набором значений истинности на множестве U будем понимать функцию . Если t(u) = T, то будем говорить, что u принимает значение “истина”, если t(u)=F, то “ложь”. Если u – некоторая переменная из множества U, то u и будем называть литералами из U. Литерал - принимает значение “истина ” относительно t в том и только в том случае, когда переменная u принимает значение “ложь”; литерал u принимает значение “истина ” относительно t в том и только в том случае, когда u принимает значение “истина”.

Дизъюнкцией над U назовём произвольное множество литералов над U, например . Она представляет дизъюнкцию этих литералов и называется выполненной при некотором наборе значений истинности тогда и только тогда, когда при рассматриваемом наборе значений истинности хотя бы один из её членов принимает значение “истина”. В нашем примере дизъюнкция будет выполнена относительно t, если одновременно не окажется, что t(u₁)=F, t(u₃)=T, t(u₈)=F.

Набор C дизъюнкций над U называется выполнимым в том и только в том случае, если найдётся некоторый набор значений истинности на множестве U, такой, что одновременно выполнены все дизъюнкции. Этот набор значений истинности назыв. выполняющим набором значений истинности для C.

Задача ВЫПОЛНИМОСТЬ формулируется следующим образом:

Заданы множество U и набор C дизъюнкции над U.

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

Например, пусть U={u₁, u₂}, C= . Эта индивидуальная задача из ВЫП имеет ответ “да”. Выполняющее задание значений истинности определяется так: t(u₁)=t(u₂)=T. Для индивидуальной задачи, в которой C= , ответ будет “нет”.

Теорема Кука формулируется следующим образом:

Задача выполнимость является NP-полной.

Доказательство результатов об 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’ множества А, такое, что .