Глава 7. Сводимость

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

Пример 32.2. Покажем сводимость задачи выполнимости КНФ к задаче о клике с указанным числом вершин (пример 30.3). Пусть КНФ F имеет вид (32.1). Построим граф G_F с k_г + k₂ + ... + k_m верши­нами, для которых используем обозначения

l_ij, i = l,2, ...,m, j = l,2,...,k_h

при этом вершины l_ij и l_vw соединяем ребром, если и только если выполнены два условия:

65535. i#v,

65535. конкретные литералы, скрывающиеся в (32.1) за обозначениями l_ij и l_vw, не являются отрицанием друг друга (скажем, если l_ij—это ­ x_ъ а l_vw— это x_ъ то эти две вершины ребром не соединяются).

Построение матрицы смежности графа G_F может быть выполнено за полиномиально ограниченное время.

Из определения клики и способа построения графа G_F следует, что клика из m вершин в этом графе существует, если и только если формула (32.1) выполнима. В самом деле, при наличии такой клики полагаем x_s = 0, когда литерал ­x_s соответствует одной из вершин клики, а в остальных случаях x_s = l. В результате каждое D_i в (32.1) равно 1.

Наоборот, если заданная формула (32.1) выполнима, то при со­ответствующих значениях всех переменных x_ъx₂, ■■■,x_n для каждого i^m можно выбрать j такое, что l_ij—это литерал со значением 1. Сделав такой выбор, мы получаем набор вершин, образующий клику с m вершинами.

Если исходная КНФ имеет вид

(-x₁v-x₂)A(x₂)A(x₁Vx₂),

то мы получаем граф G_F с пятью вершинами (рис. 25), в котором обнаруживается клика Cln, l_2i, l₃₂D с тремя вершинами. Это соответ­ствует тому, что исходная формула принимает значение 1 при x_г = 0, x₂ = 1.

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

г31

§ 32. Полиномиальная сводимость. NP-полные задачи *2i г21

а)

б)

.hi

h2*

1и.

207

hi

г32

hi

h2

Рис. 25. Построение графа G_F для вершин, б) проведение ребер.

F = ­xi v ­*₂) л (х₂) Л (jq v х₂): а) выбор

Доказано также, что задача распознавания гамильтоновости графа является NP-полной¹. Упомянем еще одну очень известную NP-пол-ную задачу, называемую задачей о рюкзаке. Задано конечное множе­ство U, размер s(u) gN⁺ и стоимость v(u) gN⁺ каждого ue U, а также a, b е N⁺. Существует ли такое подмножество U' с U, что X! s(") ^ ^а,

2 v(u)^b? ^ueU'

ue!7' ?

Из теоремы Кука следует, что для решения проблемы Р = NP доста­точно со всей тщательностью рассмотреть какой-нибудь один NP-пол-ный предикат, например, тот же предикат Sat, и ответить на вопрос о его принадлежности классу Р. Если он принадлежит классу Р, то Р = NP в силу NP-полноты рассматриваемого предиката, если не при­надлежит, то Р ф NP, так как найден предикат, принадлежащий NP и не принадлежащий Р. Но этот заманчивый план до сих пор реали­зовать не удалось, усилия многих исследователей не привели к ре­шению этой проблемы, хотя и устоялось мнение, что, скорее всего, РФ NP. Это предположение влечет за собой рекомендацию: если дока­зано, что решаемая практическая задача (при надлежащей формали­зации в виде предиката на словах в алфавите) является NP-полной, то было бы опрометчивостью рассчитывать на нахождение в короткие сроки полиномиального алгоритма ее решения, и лучше попробовать решить эту задачу приближенно.

Многие задачи фактического построения некоторого математиче­ского объекта вписываются в следующую схему: дано х; если су­ществует у такое, что х вместе с у удовлетворяют фиксированно­му условию R{x,y), то найти такое у. Соответствующая задача рас-

Огромное число примеров NP-полных задач собрано в [13].

208