Кузюрин Н.Н. Фомин С.А. Эффективные алгоритмы и сложность вычислений

Подождите немного. Документ загружается.

6.2. Полиномиальные сводимости и N P-полнота 221

6.2. Полиномиальные сводимости и N P-

полнота

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

для нее не существует полиномиального алгоритма.

Известно, что бывают алгоритмические задачи, в принципе

не разрешимые вообще никаким алгоритмом (см., например,

задачу 26 «HALT»). Поэтому естественно задаться вопросом:

а существуют ли разрешимые задачи, которые тем не менее не

принадлежат классу P? Ответ на этот вопрос предоставляется

теоремой об иерархии [67], которая наряду с теоремой Блюма

об ускорении является одним из краеугольных камней теории

сложности вычислений. Так же, как и в случае с теоремой об

ускорении, мы приводим ее упрощенный вариант.

Теорема 6.2.1. Существует алгоритмическая задача, раз-

решимая некоторым алгоритмом сложности n

O(log n)

, но не

принадлежащая классу P.

К сожалению, задачи, возникающие как в теореме об уско-

рении, так и в теореме об иерархии, носят довольно искусствен-

ный характер и по этой причине не могут быть использованы

для сложностного анализа переборных задач дискретной оп-

тимизации. Для этой цели используется теория N P-полноты,

изложение основ которой мы начинаем с понятия полиноми-

альной сводимости.

6.2.1. Сводимость по Куку

На неформальном уровне мы уже познакомились с этим поня-

тием в разделе 1.1.

Определение 6.2.1. Алгоритмическая задача P

полиноми-

ально сводится к задаче P

, если существует полиномиаль-

ный алгоритм для решения задачи P

, возможно, вызываю-

щий в ходе своей работы процедуру для решения задачи P

222 Глава 6. Основы теории сложности вычислений

При таком определении, однако, возникает один неприят-

ный эффект. Например, алгоритм 13 «Переполнение памяти

умножением», вне всякого сомнения, полиномиален, если по-

следний оператор R ← R · R понимать как вызов процедуры

умножения.

Мы уже отмечали в разделе 1.2.1, что для умножения также

существует полиномиальный алгоритм. Тем не менее, состав-

ной алгоритм 13 «Переполнение памяти умножением» непо-

линомиален, и, более того, вычисляемая им функция 2

по

очевидным причинам не принадлежит классу P. Таким обра-

зом, класс P оказывается незамкнутым относительно полино-

миальной сводимости, что, разумеется, ненормально. Понятны

и причины этого: при повторных обращениях к функциональ-

ным процедурам может происходить лавинообразный рост зна-

чений числовых параметров. Наиболее кардинальный и в то

же время общепринятый способ борьбы с этим явлением — с

самого начала ограничиться рассмотрением лишь задач разре-

шения, т. е. таких, ответ на которые имеет вид ДА/НЕТ. При

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

ются только предикатные процедуры, указанная выше пробле-

ма снимается, и класс P уже будет замкнутым относительно

полиномиальной сводимости.

Прежде чем двигаться дальше, отметим, что любую пере-

борную задачу дискретной оптимизации можно без ограниче-

ния общности заменить на переборную же задачу разрешения,

так что рассматриваемое ограничение не слишком обремени-

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

на примере задачи 4 «TSP», хотя видно, что тот же самый

метод годится для любой задачи дискретной оптимизации.

А именно, давайте вместо нахождения минимального зна-

чения суммы (1.1) ограничимся более простым вопросом: верно

ли, что Comm(m, d) ≤ B, где Comm(m, d) — минимально воз-

можная стоимость пути коммивояжера, а B — новый числовой

параметр?

6.2. Полиномиальные сводимости и N P-полнота 223

Задача 27. «TSP-разрешимость». Заданы:

• n городов c

, . . . , c

;

• d

≡ d(c

, c

) ∈ Z

— расстояния между ними;

• B — положительное целое.

Верно ли, что минимально возможное значение суммы (1.1)

меньше B?

Тогда задача 4 «TSP» допускает следующее простое поли-

номиальное сведение к этой задаче разрешения, осуществляе-

мое с помощью бинарного поиска (алгоритм 37).

В теории сложности вычислений «процедурный» вари-

ант полиномиальной сводимости называется Тьюринговой сво-

димостью или сводимостью по Куку в честь автора рабо-

ты [Кук75b].

6.2.2. Недетерминированные алгоритмы

Математическим уточнением понятия «переборная задача раз-

решения» служит «задача, разрешимая за полиномиальное

время с помощью недетерминированного полиномиального ал-

горитма».

В недетерминированных алгоритмах дополнительно раз-

решаются недетерминированные операторы перехода вида

goto `

or `

Таким образом, для каждого массива входных данных име-

ется не один, а несколько (в общем случае — экспоненциаль-

ное число) путей, по которым может развиваться вычисление.

Недетерминированный алгоритм по определению выдает окон-

чательный ответ 1, если существует хотя бы один путь раз-

вития вычисления, на котором выдается ответ 1, и 0 — в про-

тивном случае (таким образом, ответы ДА и НЕТ в случае

недетерминированных вычислений несимметричны).

224 Глава 6. Основы теории сложности вычислений

Алгоритм 37. Сведение оптимизационных задач к задачам

разрешения

Вход: n > 0, d

> 0, ∀i, j ∈ (1, . . . , n).

Выход: Перестановка π

opt

, такая, что сумма (1.1) минималь-

на.

{Используем процедуру T SP

bool

(n, D, B) для зада-

чи 27 «TSP-разрешимость»}

min

← 0

max

← n · max

1≤i<j≤n

d(c

, c

)

while B

max

− B

min

> 1 do

B ← b(B

min

+ B

max

)/2c

if T SP

bool

(n, D, B) then

max

← B

else

min

← B

end if

end while

if T SP

bool

(n, D, B

min

) then

return B

min

else

return B

max

end if

Определение 6.2.2. Недетерминированная машина

Тьюринга (НМТ) — это набор T = hk, Σ, Γ, Φi, где

• k ≥ 1 — натуральное число (число лент),

• Σ — «алфавит лент», конечное множество,

• ? ∈ Σ — алфавит содержит «пробел»,

• Γ — конечное множество состояний, ST ART, ST OP ∈ Γ,

• Φ — произвольное отношение:

Φ ⊂ (Γ × Σ

) × (Γ × Σ

× {−1, 0, 1}

6.2. Полиномиальные сводимости и N P-полнота 225

Переход из состояния g, с символами на лентах h

, . . . , h

будет допустим, если новое состояние g

, записанные

символы h

, . . . , h

и смещения головок ε

, . . . , ε

удо-

влетворяют соотношению

(g, h

, . . . , h

, g

, h

, . . . , h

, ε

, . . . , ε

) ∈ Φ.

Процесс вычисления недетерминированной машиной Тью-

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

мент «ветвления» — совершения недетерминированного пере-

хода из нескольких возможных — происходит «клонирование»

НМТ, и вычисление продолжается по всем возможным путям,

пока одной из «клонированных» НМТ не будет получен утвер-

дительный ответ («да», «1»), либо пока везде не будет получен

ответ «0».

Очевидно, детерминированные машины Тьюринга являют-

ся частным случаем недетерминированных.

Сложностью (временем работы) недетерминированного

алгоритма (НМТ) на входном слове x называется минималь-

ная сложность вычисления, приводящего на этом входе к отве-

ту «1», либо, если x /∈ L, максимальная сложность, приводящая

к «0».

Зная, что такое время работы НМТ для каждого входного

слова x, можно ввести для НМТ и сложность в наихудшем

случае.

По аналогии с определением 6.1.7 «DT IME» и опреде-

лением 6.1.10 «DSPACE» определим классы N T IME(f(n))

и N SPACE(f(n)).

Важно отметить серьезное отличие классов сложности для

НМТ и детерминированных МТ. Это замкнутость классов

сложности языков относительно дополнения для детермини-

рованных МТ и отсутствие этого свойства для НМТ.

т. е. для любого класса DT IME(f(n)) класс

coDT IME(f(n)) ≡ {L|

L ∈ DT IME(f(n))},

226 Глава 6. Основы теории сложности вычислений

состоящий из языков-дополнений

, совпадает с DT IME(f(n)).

Действительно, для любого языка L ∈ DT IME(f(n)) суще-

ствует детерминированная машина Тьюринга T с временной

сложностью f(n), и из нее, инвертировав окончательный от-

вет, получаем машину T, распознающую L и также принад-

лежащую классу DT IME(f (n)). Аналогично показывается

замкнутость относительно дополнений и классов простран-

ственной сложности детерминированных машин Тьюринга —

DSPACE(f(n)).

Для классов N T IME(f(n)) и N SPACE(f(n)) эти рассуж-

дения не проходят из-за асимметрии положительных и отрица-

тельных ответов в определении сложности НМТ, и, таким обра-

зом, нельзя утверждать о совпадении классов N T IME(f(n))

и coN T IME(f(n)), N SPACE(f(n)) и coN SPACE(f (n)).

Теперь определим важный в теории сложности класс за-

дач разрешения (языков), разрешимых полиномиальными

недетерминированными алгоритмами и его co-класс (класс-

дополнение).

Определение 6.2.3.

N P = ∪

k≥0

N T IME(n

coN P = {L|L ∈ N P}.

Упражнение 6.2.1. Покажите, что P ⊆ N P ∩ coN P.

Следует подчеркнуть, что недетерминированные алгорит-

мы представляют собой лишь некоторую довольно удобную ма-

тематическую абстракцию и, в отличие от детерминированных

и вероятностных алгоритмов, не соответствуют реально суще-

ствующим вычислительным или аналоговым машинам.

В частности, недетерминированные полиномиальные алго-

ритмы, вообще говоря, не являются эффективными, хотя и из-

вестно включение N P ⊆ PSPACE. Далее, все переборные за-

дачи лежат в классе N P. Например, задача 4 «TSP» в форме

Определение дополнения языка можно найти в разделе 7.2.

6.2. Полиномиальные сводимости и N P-полнота 227

задачи разрешения (задача 27 «TSP-разрешимость») решается

недетерминированным полиномиальным алгоритмом, который

1) недетерминировано генерирует последовательность горо-

дов для посещения (не обязательно цикл);

2) затем детерминировано проверяет:

• является ли полученный маршрут гамильтоновым

циклом;

• правда ли, что стоимость маршрута меньше B;

3) только в случае успешности обеих проверок возвраща-

ет «1», иначе — «0».

Справедливо и обратное: вычисление с помощью любо-

го недетерминированного полиномиального алгоритма можно

представить как переборную задачу (перебор ведется по всем

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

терминированных операторах перехода). Тем самым, «задача

из класса N P» оказывается адекватным математическим уточ-

нением понятия «переборная задача разрешения».

Более формально это формулируется в одном из альтер-

нативных определений класса N P через детерминированные

машины Тьюринга.

Определение 6.2.4. Язык L ⊆ Σ

∗

принадлежит классу NP,

если существуют полиномиальная детерминированная маши-

на Тьюринга M и полином p(·), такие, что

L = {x ∈ Σ

∗

: ∃ y, |y| < p(|x|)& M(x, y) = 1}.

Слово y называется обычно «подсказкой», «свидетелем»

(N P-witness), «доказательством» (N P-proof ).

Например, пусть L описывает задачу 4 «TSP» в форме за-

дачи разрешения 27 «TSP-разрешимость». Тогда слово x пред-

ставляет собой матрицу расстояний между городами и B — де-

нежное ограничение затрат на посещение всех городов, а сло-

во y будет представлять объезд всех городов с затратами < B.

228 Глава 6. Основы теории сложности вычислений

Проверить, что путь y при параметрах задачи x действитель-

но является решением, можно полиномиальным алгоритмом.

С другой стороны, если для задачи с некоторыми параметрами

такого пути (< B) нет, то, соответственно, такой подсказки

y(x

) не существует.

Существует несколько популярных определений класса N P

через сценарии совместного принятия решения двумя сторона-

ми:

1) Честным, преследующим цель установить истину, но не

гениальным, т. е. полиномиально ограниченным проверя-

ющим (человеком, королем Артуром). Эту роль обычно

обозначают veriﬁer.

2) Всемогущим консультантом (магом Мерлином, ораку-

лом), который в силах предложить правильное решение,

но может предложить неправильное (например, пресле-

дуя свои интересы или лоббируя чужие). Эту роль обыч-

но обозначают oracle или prover.

Соответственно, класс N P — это класс языков, разрешимых

такой командой, в которой оракул предлагает решения, но

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

«юридическую» силу (оракул может и обмануть).

Обратите внимание на следующие моменты:

1) полиномиальную ограниченность подсказки, — полино-

миальности проверяющего алгоритма A недостаточно,

т.к. он полиномиален относительно длины своих аргу-

ментов x и y. т. е. краткость подсказки важный момент —

подсказки, вроде «а проверь все маршруты», которые,

безусловно, можно проверить за полиномиальное время

от длины описания «всех маршрутов», не подойдут, если

длина описания этого множества маршрутов экспоненци-

альна;

6.2. Полиномиальные сводимости и N P-полнота 229

2) если элемент не принадлежит языку, то подсказки с ука-

занными свойствами не должно существовать, т. е. ничто

не заставит проверяющего ошибиться.

Через определение 6.2.4 «N P/ДМТ» еще легче увидеть

«переборную» сущность класса N P, т.к. видно, что можно

перебирать детерминированным алгоритмом множество вари-

антов, эффективно (полиномиальным алгоритмом) проверяя

каждый вариант.

Теорема 6.2.2. Определение 6.2.3 «N P/НМТ» и определе-

ние 6.2.4 «N P/ДМТ» эквивалентны.

Доказательство. 6.2.3 «N P/НМТ» → 6.2.4 «N P/ДМТ».

Для каждого слова x ∈ L подсказкой y можно назна-

чить закодированный кратчайший протокол выполнения-

подтверждения НМТ T, определяющей язык L, в смысле

определения 6.2.3 «N P/НМТ». Так как длина кратчайше-

го пути-подтверждения T(x) полиномиально ограничена, то

можно выбрать полиномиально ограниченную кодировку y(x).

Проверить целостность протокола (отсутствие противоречий

с определением НМТ T) y(x) можно также за полиномиальное

время.

6.2.4 «N P/ДМТ» → 6.2.3 «N P/НМТ». Еще проще. Пусть

НМТ T недетерминированно дописывает разделитель #

и некоторое слово y к входному слову x, а затем работает над

словом x#y как полиномиальная детерминированная машина

Тьюринга из определения 6.2.4 «N P/ДМТ».

6.2.3. Сводимость по Карпу

Понятие полиномиальной сводимости по Куку

оказывается

чрезмерно общим для изучения переборных задач ввиду от-

меченной выше асимметрии ответов 1 и 0.

см. определение 6.2.1 «Сводимость по Куку».

230 Глава 6. Основы теории сложности вычислений

Например, задача разрешения «Comm(m, d) > B» (в кото-

рой спрашивается «верно ли, что любой маршрут коммивоя-

жера имеет длину по крайней мере (B + 1)?») принадлежит

классу coN P и не принадлежит классу N P при общепринятой

гипотезе P 6= N P. В то же время она очевидным образом сво-

дится по Куку к переборной задаче 27 «TSP-разрешимость»,

принадлежащей классу NP.

Поэтому в теории сложности вычислений гораздо большее

распространение получил ограниченный вариант полиноми-

альной сводимости по Куку, впервые рассмотренный в осно-

вополагающей работе [Кар75a] и, соответственно, называемый

сводимостью по Карпу (мы будем использовать для нее про-

сто термин полиномиальная сводимость, также широко рас-

пространенный в литературе).

Определение 6.2.5. Задача разрешения P

полиномиально

сводится к задаче разрешения P

, если

• существует полиномиально вычислимая функция f : I

→ I

(отображает входные данные I

для P

во входные дан-

ные I

≡ f(I

) для задачи P

• ∀I

совпадают ответы на вопросы «P

)?» и «P

(f(I

))?».

Легко видеть, что относительно такого усеченного варианта

полиномиальной сводимости класс переборных задач разреше-

ния N P уже оказывается замкнутым.

Фундаментальной открытой проблемой теории сложности

вычислений (а к настоящему времени и одной из наиболее

фундаментальных проблем всей современной математики —

[Sma00]) является вопрос о совпадении классов сложности P

и NP . Иными словами, все ли переборные задачи можно ре-

шить с помощью эффективного алгоритма? В связи с этой ем-

кой формулировкой P

= N P-проблему еще называют иногда

проблемой перебора.