4.7. Основная теорема (Cook, 1971)

Задача разрешимости логического выражения является NP-сложной.

Итак, данная теорема утверждает, что решение любой задачи из класса NP (т. е. такой задачи, которую можно обработать на НДМТ за полиномиальное время) может быть получено из решения задачи разрешимости с помощью некоторой трансформации, которая тоже полиномиальна. Или, иначе, для решения произвольной задачи класса NP достаточно уметь решать задачу разрешимости:

Любая задача класса задача разрешимости.

Этот результат впервые получен Куком (1971 г.) в связи с изучением вопросов автоматического доказательства теорем и является более тонким математическим результатом по сравнению с классическими теоремами о неразрешимости в формальных системах [Church, 1932; Godel, 1931; см. гл. 3].

При доказательстве этой теоремы, которое мы приведем ниже, нам придется уточнить формальную модель НДМТ.

Недетерминированная машина Тыоринга (НДМТ) состоит из считывающе-записывающей головки, регистрирующей ленты, разделенной на ячейки, в которых записаны символы или Она характеризуется конечным множеством внутренних состояний и семью свойствами:

1) в каждый момент времени головка имеет доступ только к одной ячейке регистрирующей ленты;

2) в любой момент времени каждая клетка содержит один символ;

3) в данный момент допускается только одно состояние;

4) изменять можно только ячейку, находящуюся под головкой;

5) остальные действия (перемещение головки, изменение внутреннего состояния, инструкция “ВЫБОР”) могут быть выполнены только с помощью функции определяющей машину М;

6) исходным состоянием может быть любое возможное состояние;

7) конечным называется состояние, связанное с первым успехом (по отношению к последней неудаче).

Теперь, когда задана недетерминированная машина Тьюринга М, описываемая по предложенной выше схеме, и, помимо этого, задача произвольной размерности которую можно решить на этой машине, мы построим в явном виде логическое выражение Ем, такое, что

Важным моментом является то, что доказательство разрешимости выражения Ем, можно проводить с помощью любого полиномиального алгоритма. можно решить на М за полиномиальное время” означает, что существует по крайней мере одна последовательность состояний где

• — является “законным ходом”};

• — исходное состояние;

• — конечное состояние, причем где — некоторый полином;

• никакая другая законная цепочка состояний не имеет больше чем ячеек, т. е. в ней не более шагов.

Выражение которое мы построим ниже, будет имитировать цепочку В него войдет ряд переменных. Каждое присваивание значений этому множеству упеременных соответствует не более чем одной последовательности законных состояний. И наконец, значение ИСТИНА данное выражение принимает тогда и только тогда, когда существует набор значений, который соответствует последовательности, приводящей к успеху.

Используем такие переменные, которые допускают точное описание рассматриваемой НДМТ; они бывают трех типов.

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

тогда и только тогда, когда в момент времени 0 машина М находится в состоянии причем это состояние является единственным (, где — число возможных состояний из множества ).

• тогда и только тогда, когда в момент времени ячейка на регистрирующей ленте машины М содержит символ , наконец,

Число символов постоянно и не зависит от так что число введенных логических переменных составляет т. е. является полиномом, зависящим от задачи, размерность которой на входе составляет

Теперь свойствам машины М 1—7 мы поставим в соответствие семь логических выражений —

Головка проверяет одновременно только одну ячейку.

Это выражение содержит термов; следовательно, условие А записывается с помощью термов.

B. В любой момент времени в каждой клетке имеется только один уникальный символ.

Мы получаем

Поскольку не зависит от условие В записывается с помощью термов.

C. М может находиться в данный момент только в одном состоянии.

Условие С записывается с помощью термов, так как число состояний не зависит от машины М.

D. На ленте может изменяться только ячейка, находящаяся под головкой.

т. е. если ячейка находится под считывающей головкой машины М и в ней содержится символ то

• либо головка считывает ячейку в момент времени 0;

• либо в момент времени ячейка все еще содержит 6-й символ.

Это хорошо согласуется с условиями А и В. Условие записывается с помощью символов, поскольку — константа.

E. Каждое новое состояние может быть получено только с помощью функции определяющей машину М, т. е. в момент времени 0:

ячейка содержит символ

головка считывает ячейку а М находится в состоянии следующее состояние является одним из состояний

Это утверждение типа мы будем записывать в виде у или в данном случае после преобразования трех посылок:

где обозначает произвольное состояние из

Поскольку машина является недетерминированной, для любой тройки существует более чем одна тройка но при этом таких троек всегда конечное число.

Таким образом, для фиксированных и независимо от приведенное выше выражение имеет ограниченную длину. Поскольку число состояний само является постоянным, условие Е записывается с помощью термов.

F. Исходное состояние является законным, т. е. когда мы обозначаем с помощью индекса 1 состояние в момент времени

1, самая левая ячейка автоматически получает номер 1:

Кроме того, ячейки с номерами от 2 до содержат исходное условие а другие — пусты, т. е. если пустой символ закодирован единицей, то

Следовательно, условие имеет длину

Свойство 7 утверждает, что в конечном счете существует искомое состояние , представляющее собой успешное завершение работы алгоритма.

Допуская, что начиная с этого момента машина остается в данном состоянии (конкретно М будет находиться в состоянии в момент времени мы получим и

Полное условие Н для решения задачи с помощью машины М записывается в виде

По построению данное условие выражается с помощью не более чем термов, причем оно является выполнимым тогда и только тогда, когда машина М решает задачу Действительно, если последовательность состояний ведет к тем самым определены те значения переменных которые присваивают Н значение ИСТИНА. И наоборот, если значения переменных известны, через функцию они соответствуют последовательности законных состояний.

Так как мы не накладывали на нашу недетерминированную машину М никаких ограничений, мы доказали, что любая задача, которую можно решить на М (любой язык, понимаемый машиной М), полиномиально сводима к задаче разрешимости логического выражения.