Теорема Кука: первая NР - полная задача

 

Исторически первой задачей, для которой С. Куком [7] было дано доказательство NР - полноты, была задача выполнимости КНФ (конъюнктивной нормальной, формы). КНФ называется формула вида

(5.1)

 

Задача выполнимости состоит в том, чтобы по заданной КНФ узнать, обращается ли реализуемая ею функция алгебры логики в единицу хотя бы на одном наборе значений переменных . Будем обозначать эту задачу .

Теорема_5.1. (Сoоk S.A., 1971).

Задача выполнимости КНФ является NР- полной.

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

Достаточно убедиться, что:

а) и

б) что любая задача из NР полиномиально сводится к

а) Недетерминированный алгоритм, решающий задачу при длине КНФ, равной m, и числе переменных n, состоит в следующем::

 

-недетерминированным оператором выбрать ;

- просмотреть в каждой из m скобок не более, чем n значений

литералов и дать ответ «выполнима», если в каждой скобке найдется хотя бы один литерал, принимающий значение 1, иначе дать ответ «не выполнима».

Очевидно, для этого недетерминированного алгоритма сложность

может быть оценена как o(mn) и является полиномиальной, поэтому

.

б) Покажем, что любая задача из NP полиномиально сводима к

.

Сначала отметим, что любая задача вычисления свойств может быть представлена следующим образом: по заданному объекту х, выяснить, существует ли объект у такой, что R(x,y)=1. В нашей задаче объект х - формула, а у - набор значений переменных. Свойство R(x,y) состоит в том, что на наборе у формула х выполнима. Любая задача из NP может быть сформулирована как задача вычисления свойства. Суть дальнейшего доказательства состоит в указании процедуры, которая для любого полиномиального недетерминированного алгоритма вычисления свойства (выходом которого являются ответы «истина» или «ложь») и для любой допустимой начальной информации такого алгоритма строит одно логическое выражение в виде КНФ, которое является выполнимым тогда и только тогда, когда алгоритм определяет ответ «истина», причем построение этого логического выражения из формального описания недетерминированного алгоритма и его входной информации можно выполнить за полиномиальное число шагов.

Построение этой процедуры выполняется в терминах алгоритмической системы Тьюринга.

Итак, произвольная задача z вычисления свойства R(x,y) из

 

класса NР может быть выполнена на НДМТ с полиномиальной проверкой, т.е. за число шагов, ограниченное полиномом от размера задачи l(х)+l(y) = n. Полиномиальной при этом будет и длина рабочей зоны ленты НДМТ Т = Р(n) P(,) - некоторый полином, ячейки НДМТ обозначим целочисленными номерами.... -2, -1, 0,+1,+2,.... Расположение начальной информации на ленте представлено на рис. 5.1. в ячейках с номерами 1,……, n

произвольное начало отсчета

…

-2

-1

…

n

…

начальная информация

Рис. 5.1

Вычисления при любом допустимом значении объекта у происходят в зоне ленты [-Т, Т] и завершаются не более чем за Т шагов (тактов работы НДМТ). Машина начав работу в конфигурации останавливается в конфигурации , если свойство R(x, y) выполнено, и в - в противнем случае.

Построим КНФ Ф, такую, что любая задача проверки (распознания) свойства - в общем виде:

- полиномиально сводится к проверке выполнимости КНФ

Ф = В & C & D & Е & F & G,

где В, С, D, E, f, g - дизъюнкты, имеющие следующий смысл:

В = 1 • на каждом шаге головка машины обозревает ровно одну ячейку ленты:

 

С = 1 • в каждой ячейке на каждом шаге записан в точности один символ;

D = 1 • на каждом шаге работы машина находится ровно в

одном состоянии;

Е = 1 • начальная конфигурация машины имеет вид ;

F = 1 • машина работает по тьюринговской программе;

G = 1 • заключительная конфигурация машины имеет вид ,

если Р(х,у) = 1.

Обозначим , - внешний

и внутренний алфавиты НМДТ; t - шаги выполнения алгоритма,

; s - номера ячеек, ; i и j - текущие номера символов алфавитов А и Q, , .

Введем следующие логические переменные:

, если на шаге t, обозревая ячейку s,. машина воспринимает символ с номером 1, иначе эта переменная равна нулю;

, если на шаге t машина находится в состоянии с номером j,

иначе эта переменная равна нулю.

, если на шаге t головка машины обозревает ячейку с

номером s, иначе эта переменная равна нулю.

Используя введенные логические переменные, можно записать в виде формул следующие логические условия;

 

на шаге t машина обозревает хотя бы одну ячейку и при этом

 

никакие две одновременно, т. к.

Тогда

 

 

на шаге t в ячейке s записан ровно один символ. Тогда

 

 

 

на шаге t машина находится ровно в одном состоянии. Тогда

 

 

 

В начальном положении (t=0) головка машины обозревает ячейку с номером 1 в состоянии q1, а в первых n - ячейках записаны символы слова Х = х(1)...х(n), за ним - разделительный знак «*», после чего - слово Y и далее - пустые ячейки. Выполнение такой начальной конфигурации равносильно Е = 1, где

 

 

где l - пустой символ.

Полиномиальная программа проверки свойства состоит из тьюринговских команд: