Теорема Кука

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

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

Доказательство этой теоремы, полученное Стивеном Куком в его фундаментальной работе в 1971 году, стало одним из первых важнейших результатов теории NP-полных задач. Независимо в то же время эта теорема была доказана советским математиком Леонидом Левиным.

В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к КНФ. С. Кук определил класс NP задач распознавания свойств следующим образом. Задача принадлежит классу NP, если:

- решением задачи является один из двух ответов: «да» или «нет» (задача распознавания свойств);

- требуемый ответ может быть получен на недетерминированном вычислительном устройстве за полиномиальное время.

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

Задача ВЫПОЛНИМОСТЬ является NP-полной.

Лекция 7 Шесть основных 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’, такое, что.

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