22. Np- полные задачи. Теорема Кука-Карпа-Левина. Np-полнота задачи о клике

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

Если хотя бы одна NP-полная задача полиномиально разрешима, то P = NP

NP-полные задачи – это самые сложные задачи (не удастся найти для неё полиномиальный алгоритм) Если А – NP- полная и AB, то В – NP- полная

1)Задача “3-Выполнимость”

Вход: булева функция f(x₁,…,x_n), заданная в виде КНФ, причем все ЭД содержат ровно 3 переменные.

Вопрос: существует ли такие x₁,…,x_n , что f(x₁,…,x_n)=1?

2)Задача “Клика”

Вход: граф G и натуральное число k

Вопрос: содержит ли граф клику размера k?

3)Задача “Вершинное покрытие”

Вход: граф G и натуральное число k

Вопрос: содержит ли граф вершинное покрытие размера k?

4)Задача “3-мерное сочетание”

Вход: Множество MXYZ, |X|=|Y|=|Z|=q

Вопрос: существует ли подмножество NM такое, что |N| = q и никакие два элемента из N не имеют ни одной равной координаты (т.е. для любых (a,b,c), (u,v,w)N,a≠u,b≠v,c≠w)?

5)Задача “Гамильтонов цикл”

Вход: граф G

Вопрос: существует ли цикл, проходящий через каждую вершину графа ровно 1 раз (гамильтонов цикл)

6)Задача “Разбиение”

Вход: массив X из n натуральных чисел x₁,…,x_n

Вопрос: можно ли разбить X на два подмассива Y и Z таких, что суммы их элементов равны?

Задача “Выполнимость”

Вход: булева функция f(x₁,…,x_n), заданная в виде КНФ

Вопрос: существует ли такие x₁,…,x_n , что f(x₁,…,x_n)=1?

Теорема Кука-Карпа-Левина. Задача “SAT”(Задача “Выполнимость”) является NP-полной.

Теорема. Задача “Клика” является NP-полной.

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

Докажем сначала, что “Клика”NP. Сведем к задаче “Клика” задачу “3-выполнимость”. Пусть F= C₁&…&C_k – вход задачи “3-выполнимость”,

где С_i – это ЭД.

Литерал – это либо переменная, либо отрицание переменной.

Каждая ЭД C_i содержит ровно 3 литерала. Посторим граф G следующим образом. и если и только если rs и литералы, соответствующие этим вершинам, не являются отрицаниями друг друга.

Теперь нам нужно показать, что F выполнима тогда и только тогда, когда в построенном графе есть клика порядка k. Пусть F выполнима. Тогда после подстановки соответствующего набора переменных в каждой ЭД должен быть истинный литерал. Пусть это литералы . Покажем, что - клика. Действительно, все эти литералы взяты из разных ЭД. Кроме того, они все равны 1 => никакие 2 из них не могут быть отрицаниями друг друга.

Обратно, пусть в построенном графе есть клика порядка k. Эта клика содержит ровно по одной вершине из каждой тройки. Если литерал, соответствующий вершине клики – это отрицание, то присвоим соответствующей переменной значение 0. Если же этот литерал – не отрицание, то присвоим значение 1. Могло бы получиться противоречие, если бы в клику входили два литерала, один из которых равен x₁, а другой – отрицанию x₁. Но такого не будет по определению графа.