18.2. NP-полные задачи. Теорема Кука

Если P ¹ NP, то задачи из NP\P являются труднорешаемыми. Цель дальнейших результатов состоит в доказательстве того, что существуют конкретные задачи П, для которых справедливо включение П Î NP\P, если P ¹ NP. Соответствующие результаты основаны на понятии полиномиальной сводимости задач. Пусть П1, П2 — две задачи распознавания, задаваемые в алфавитах А1 и А2 соответственно. Будем говорить, что задача П1 полиномиально сводится к задаче П2 (обозначение: П1 µ П2), если существует словарная функция такая, что выполнены условия:

F — полиномиально вычислима;

выполнено: Х — индивидуальная задача П1 с ответом «ДА» Û — индивидуальная задача П2 с ответом «ДА».

Утверждение 18.2. Если выполнено П1 µ П2 и П2 Î P, то П1 Î P.

Доказательство. Предложим полиномиальный алгоритм решения задачи П1: находим F(X) Î П2 и применяем к F(X) полиномиальный алгоритм, существующий по условию. Если получен ответ «ДА», то Х имеет ответ «ДА». В противном случае Х имеет ответ «НЕТ». Время работы алгоритма не превосходит , где PF — полином, ограничивающий время вычисления функции F, участвующей в сведении П1 µ П2, P2 — полином, ограничивающий время решения задачи П2. Доказательство завершено.

Утверждение 18.3. Если выполнено П1 µ П2 и П2 µ П3, то П1 µ П3.

Доказательство очевидно, так как функция F3(X) = F2(F1(X)) осуществляет сведение П1 µ П3, если F1, F2 дают сведения П1 µ П2, П2 µ П3 соответственно.

Определение 18.4. Задача П называется NP-Полной, если выполнено:

А) П Î NP;

Б) П1 µ П для любой задачи П1 Î NP.

Задача П называется NP-Трудной, если для нее выполнено условие б).

Обозначим через NPС класс NP-полных задач, а через NPН — класс NP-трудных задач.

Согласно определению имеем:

NPС Ç P ¹ Æ Þ P = NP,

NPH Ç P ¹ Æ Þ P = NP,

NPС Ç (NP\P) ¹ Æ Þ NPС Ç P = Æ.

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

Утверждение 18.4. Если задачи П1, П2 ΠNP, П1 µ П2 и П1 ΠNPС, то П2 ΠNPС.

Доказательство. Пусть П’ Î NP — произвольная задача. Тогда по определению П’ µ П1. Поскольку по условию П1 µ П2, то согласно утверждения 18.3 имеем П’ µ П2, что и доказывает данное утверждение.

Отсюда получаем способ доказательства NP-полноты конкретных задач, используя полиномиальное сведение к ней другой NP-полной задачи. Этот же способ пригоден и для доказательства NP-трудности задачи. Напомним, что классы NPC и NPH определяются только выполнимостью условий а), б) для NPC и условия б) для NPH.

Докажем теперь важную теорему Кука С. (1971), дающую первый пример NP-полной задачи.

Теорема 18.5. Задача проверки выполнимости произвольной КНФ является NP-полной задачей.

Доказательство. Пусть ВЫП — идентификатор данной задачи. В предыдущем разделе было показано, что ВЫП Î NP. Пусть П — произвольная задача из NP. Необходимо показать, что П µ ВЫП. Для этого множество индивидуальных задач LП с ответом «ДА» представим в стандартном виде соответствующей недетерминированной машиной Тьюринга (обозначение: НДМТ), работающей полиномиальное время и принимающей множество LП. Такое представление дает общую сводимость задачи, решаемой НДМТ за полиномиальное время.

Пусть распознающая множество LП НДМТ имеет алфавиты А, Q и функцию переходов (программу) , Р(N) — верхняя граница времени вычисления. Функцию FL, осуществляющую полиномиальное сведение П µ ВЫП, опишем в терминах работы НДМТ.

В вычислениях участвуют ячейки ленты с номерами от -Р(N) до Р(N) + 1, и при этом требуется учесть не более Р(N) + 1 тактов работы НДМТ. Проверяющее вычисление определяется заданием в каждый момент времени содержания ячеек с указанными номерами, внутреннего состояния машины и положения считывающей головки. Соответствующие вычисления опишем в виде КНФ, использующей полиномиальное число дизъюнкций. Фиксируем нумерацию в алфавитах:

.

Условимся, что фраза «в момент времени I» означает «после выполнения I-го шага работы». Если вычисление закончилось раньше времени P(N), то конфигурация не меняется во все моменты после остановки. В нулевой момент на ленте записано слово Х в ячейках с номерами 1, …, N. Слово-догадка W пишется в ячейках с номерами –1, …, –|N|. Остальные ячейки пусты. Описывая принимающее вычисление, необходимо учесть, что:

А) в ячейках пишется точно один символ;

B) машина находится точно в одном состоянии;

С) головка может просматривать точно одну ячейку с номером от –P(N) до P(N) + 1;

D) машина работает по программе.

Определим сначала переменные и их смысл с помощью табл.18.2.

Таблица 18.2

Переменная	Пределы изменения индексов	Смысл
Q(I, K)	0 £ I £ P(N) 0 £ K £ R	В момент времени I машина находится в состоянии QK
H(I, J)	0 £ I £ P(N) –P(N) £ J £ P(N) + 1	В момент времени I головка просматривает ячейку с номером J
A(I, J, K)	0 £ I £ P(N) –P(N) £ J £ P(N) + 1 0 £ K £ R	В момент времени I в J-ю ячейку записан символ AK

Описание сводящей функции FL для П µ ВЫП дадим в виде набора дизъюнкций, конъюнкцией которых и будет FL. При этом выполняющий набор значений истинности однозначно соответствует принимающему вычислению на Х, стадия проверки занимает время не большее P(N) шагов, слово-догадка имеет длину не более P(N), причем:

X Î LП Û на Х существует принимающее вычисление;

Û на Х существует принимающее вычисление с временем £ P(N) и |W| £ P(N);

Û существует выполняющее значение переменных для задачи FL(X), заданной КНФ.

При этом FL(X) вычисляется за полиномиальное время.

Определим множества дизъюнкций и их смысл.

G1 в любой момент времени I машина находится точно в одном состоянии;

G2 в любой момент времени I головка просматривает точно одну ячейку;

G3 в любой момент времени I каждая ячейка содержит точно один символ А;

G4 в момент времени 0 вычисление находится в начальной конфигурации стадии проверки со входом Х;

G5 не более чем через P(N) шагов машина переходит в состояние QY (принимает Х);

G6 для любого момента времени I, 0 £ I £ P(N) конфигурация машины в момент I + 1 получается из конфигурации в момент I однократным применением команды машины.

Описание дизъюнкций для функции FL.

G1	(Q(I, 0) Ú Q(I, 1) Ú … Ú Q(I, R))	0 £ I £ P(N)
	0 £ I £ P(N) 0 £ I < J’ £ R
G2	(H(I, ‑P(N)) Ú H(I, ‑P(N) + 1) Ú … Ú Ú H(I, P(N) + 1))	0 £ I £ P(N)
	0 £ I £ P(N) –P(N) £ I < J’ £ £ P(N) + 1
G3	(A(I, J, 0) Ú A(I, J, 1) Ú … Ú A(I, J, V)	0 £ I £ P(N)
	‑p(N) £ J £ P(N) + 1 0 £ K < K’ £ V
G4	(Q(0, 0)), (H(0, 1)), (A(0, 0, 0)), (A(0, ‑1, 0)), …, (A(0, ‑P(N), 0)), (A(0, 1, K1)), …, (A(0, N, KN)), (A(0, N + 1, 0)), …, (A(0, P(N) + 1, 0)), Где
G5	(Q(P(N), 0))
G6	А) Замечание. Дизъюнкция гарантирует, что если головка машины в момент I не просматривает ячейку J, то в момент I + 1 ее содержимое не меняется	0 £ I £ P(N) ‑p(N) £ J £ P(N) + 1 0 £ L £ V
Б) , Где D, L, K’ определены командами машины: Если QK ΠQ\{QY, QN}, то QK AL à QK’ AL’D; Если QK Î {QY, QN}, то D = 0, K’ = K, L’ = K	0 £ I £ P(N) ‑p(N) £ J £ P(N) + 1 0 £ L £ V

Заметим, что число дизъюнкций в G6 — полином от N. Далее, если X Î LП, то существует принимающее вычисление длины не большей P(N) и выполнимы все дизъюнкции из G1, G2, G3, G4, G5, G6, и X Î LП тогда и только тогда, когда существует выполняющий набор для FL = G1× G2× G3× G4× G5× G6. Теперь, для любого X Î LП индивидуальная задача FL(X) может быть построена за время, ограниченное полиномом от N = |X|, при этом длина FL(X) также ограничена сверху полиномом от N.

Таким образом, преобразование FL(X) может быть осуществлено за число действий, полиномиально зависящее от N. При этом FL(X) имеет O((P(N))2) переменных и O((P(N))2) дизъюнкций. Так как П — произвольная задача из NP, то тем самым теорема доказана.

< Предыдущая		Следующая >