NP-полнота Теорема Кука

Полиномиальная сводимость Пусть Π 1 =(X 1,Y 1 ) и Π 2 =(X 2,Y 2 ) задачи распознавания. Будем говорить, что Π 1 полиномиально сводится (по Карпу) к Π 2, если существует функция f : X 1 X 2, вычислимая в полиномиальное время такая, что f(x) Y 2 для всех x Y 1, и f(x) X 2 \Y 2 для всех x X 1 \Y 1.

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

Набор значений истинности Пусть U={u 1, u 2,…, u k }множество булевых переменных. Под набором значений истинности на множестве U будем понимать функцию T: U {true, false}. Расширим T к множеству, полагая если и наоборот. Элементы множества L называются литералами.

Дизъюнкция Дизъюнкцией над U называется множество литералов над U. Она представляет дизъюнкцию этих литералов и называется выполненной при некотором наборе значений истинности тогда и только тогда, когда при рассматриваемом наборе значений истинности хотя бы один из ее членов принимает значение true. Семейство (набор) Z дизъюнкций над U называется выполнимым в том и только том случае, если найдется некоторый набор значений истинности на множестве U, такой что выполнены все дизъюнкции из Z.

Задача «Выполнимость» Условие. Задано множество переменных U и набор Z дизъюнкций. Вопрос. Является ли Z выполнимым?

Теорема Кука (1971) Теорема 2.1 Задача «Выполнимость» является NP-полной.

Доказательство «Выполнимость» NP.

Доказательство сводимости Пусть Π=(X,Y) будет любая другая проблема в NP. Требуется доказать, что Π полиномиально сводится к «Выполнимости». По определению существует полином p и задача распознавания Π'=(X',Y') из P, такие что X' = {x#c: x X, c {0,1} p(size(x)) } и Y = {y X : c {0,1} p(size(x)) : y#c Y'}. Пусть Φ:{0,…,N}× A { }{-1,…,N}×A { }×{-1,0,1} – полиномиальная машина Тьюринга для Π' с алфавитом A. Пусть полином q : time(Φ,x#c) q(size(x#c)) для всех примеров x#c X'. size(x#c) = size(x) p(size(x))

Основная идея Сконструировать набор Z(x) дизъюнкций над множеством V(x) булевых переменных для каждого x X, так что Z(x) выполнимо тогда и только тогда, когда x Y.

Булевы переменные Q:=q(size(x) p(size(x)) ) V(x): –v ijσ, 0 i Q, -Q j Q и σ A { }= (после i шагов вычислений в j-й позиции строки записан символ σ); –w ijn, 0 i Q, -Q j Q и 1 n N; (после i шагов вычислений j-я позиция строки просматривается и оператор n выполняется).

Итоговая цель Если (n (i),s (i),π (i) ) i = 0,1,2,… тройка из вычисления Φ, то требуется определить набор дизъюнкций таким образом, что –v ijσ = true s j (i) =σ; –w ijn = true π (i) = j и n (i) = n; –набор Z(x) дизъюнкций выполним существует строка c, такая что output(Φ,x#c)=1.

Требуемые условия для выполнимого набора дизъюнкций На каждом шаге вычислений каждая позиция содержит единственный символ. На каждом шаге вычислений ровно одна позиция просматривается, и один оператор выполняется. Вычисление начинается со входа x#c для некоторого c {0,1} p(size(x)). Алгоритм работает корректно. ( (n,σ)=(m,τ,δ)) Алгоритм останавливается, если n (i) = 1. Не просмотренные позиции не изменяются. Алгоритм на выходе получает 1.

На каждом шаге вычислений каждая позиция содержит единственный символ.

На каждом шаге вычислений ровно одна позиция просматривается, и один оператор выполняется.

Вычисление начинается со входа x#c для некоторого c {0,1} p(size(x)).

Алгоритм работает корректно. ( (n,σ)=(m,τ,δ)).

Алгоритм останавливается, если n (i) = 1.

Не просмотренные позиции не изменяются.

Алгоритм на выходе получает 1. {v Q,1,1 }, {v Q,2, }

Полиномиальность сведения Длина записи Z(x) O(Q 3 log Q) –Число литералов O(Q 3 ) –запись индекса O(log Q) Так как Q это полином от size(x), то существует полиномиальный алгоритм, который по данному x, вычисляет Z(x). Осталось доказать, что Z(x) выполнима тогда и только тогда, когда x Y.

Z(x) выполнима. набор значений истинности T, на котором выполнены все дизъюнкции. Пусть c {0,1} p(size(x)), и c j = 1 для всех j c T(v 0,size(x)+1+j,1 ) = true, и c j = 0 для всех j c T(v 0,size(x)+1+j,1 ) = false. По построению переменные отражают вычисление на входе x#c. output(, x#c)=1. алгоритм проверки сертификата. x «да»-пример (x Y).

x Y и c любой сертификат для x. Пусть (n (i),s (i),π (i) ) i = 0, 1, …, m вычисление Φ x#c. T(v i,j,σ ) = true s j (i) = σ T(w i,j,n ) = true π (i) = j и n (i) = n. T(v i,j,σ ) = T(v i-1,j,σ ) i = m + 1,…, Q. T(w i,j,n ) = T(w i-1,j,n ) i = m + 1,…, Q. T набор значений истинности, на котором выполнены все дизъюнкции из Z(x).

Задача «3-Выполнимость» Условие. Задано множество переменных U и набор Z дизъюнкций, каждая из которых содержит ровно 3 литерала. Вопрос. Является ли Z выполнимым?

3-Выполнимость Теорема 2.2 (Cook 1971) Задача «3-Выполнимость» является NP-полной.