2.2. Полиномиальная сводимость задач

Пусть даны две массовые задачи распознавания Z и Z'. Будем говорить, что задача Z полиномиально сводима к задаче Z' (обозначается Z µ Z'), если существует алгоритм A, который переводит описание любой индивидуальной задачи z Î Z в описание индивидуальной задачи z' Î Z', и при этом:

1) эти индивидуальные задачи эквивалентны, т.е. либо обе имеют ответ «Да», либо обе «Нет»;

2) время работы алгоритма A ограничено некоторым полиномом P(l), где l – длина описания задачи z; очевидно, что той же величиной P(l) будет ограничена и длина описания задачи z'.

Если для двух массовых задач Z и Z' имеет место полиномиальная сводимость Z µ Z', то можно утверждать следующее:

1) если задача Z' полиномиальна, то и Z тоже полиномиальна (или короче: Z' Î P Þ Z Î P);

2) если Z не является полиномиальной, то и Z' тоже не является (Z Î ~P  Z' Î ~P).

Докажите сами эти несложные утверждения. Подсказка: суть дела в том, что полином от полинома – это тоже полином. Почти стихи.

Запомните твердо, где в этих утверждениях Z, а где Z'. Лучше не зазубривать, а понять.

Отметим также транзитивность отношения полиномиальной сводимости: если Z₁ µ Z₂ и Z₂ µ Z₃, то Z₁ µ Z₃. Докажите сами.

2.3. Недетерминированные машины Тьюринга и np-задачи

Вспомним определение обычной МТ. Имеется бесконечная лента, в ячейках которой записаны буквы из алфавита A = {a₁, a₂, ... a_m}, задано множество состояний машины Q = {q₁, q₂, ... q_n} и множество правил перехода R = {q_ia_j ® q'_ia'_jd_k}, где d_k - сдвиг ленты, d_k Î {L, R, E}. Задано начальное состояние и заключительное состояние q₀. Слегка изменим это определение, введя два заключительных состояния q_y и q_n, соответствующих двум возможным ответам в задаче распознавания. Как говорилось выше, любая задача распознавания принадлежит либо классу P, либо классу ~P, в зависимости от того, существует ли МТ, решающая эту задачу за время, не превышающее P(l) тактов, где P - некоторый полином, l - длина описания индивидуальной задачи (это обозначается так: l = |z|). Плохо только то, что для многих важных задач неизвестно, существует ли полиномиальный алгоритм их решения.

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

Удобно представлять себе работу НМТ таким образом, как будто выбираются сразу все правила с подходящей левой частью. Машина как бы размножается в нескольких экземплярах, каждый из которых выполняет переход по одному из допустимых правил. Далее все экземпляры работают независимо и могут опять размножаться, если возникает неоднозначность выбора правила. Таким образом, если поведение детерминированной МТ можно представить линейной траекторией переходов из состояния в состояние, то поведение НМТ можно изобразить деревом. Часть ветвей дерева могут быть конечны (экземпляры НМТ приходят в заключительное состояние), другая часть – бесконечны (экземпляры циклятся). Количество ветвей может быть неограниченно большим.

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

Чтобы не удивляться таким странным свойствам НМТ, следует понимать, что она представляет собой чисто математическое понятие. Детерминированную МТ можно рассматривать как модель вполне реального вычислительного устройства, которое при необходимости может быть реализовано «в железе» или программно (при замене только понятия «бесконечная лента» на «достаточно длинная лента»). Напротив, НМТ нельзя реализовать аппаратно – не хватит материала. Промоделировать НМТ программно – можно, но с очень большой потерей скорости и расходом памяти из-за необходимости имитировать параллельное выполнение неограниченного количества ветвей. Итак, НМТ – это абстрактная математическая модель, используемая для исследования свойств алгоритмов.

Любая конкретная НМТ, как и детерминированная МТ, решает некоторую массовую задачу распознавания Z, при этом в начальном состоянии лента содержит описание индивидуальной задачи z Î Z. Будем говорить, что индивидуальная задача принимается данной детерминированной МТ, если через конечное число тактов МТ достигает состояния q_y. Наоборот, задача не принимается, если МТ приходит в состояние q_n или вообще не останавливается (обратите внимание на асимметрию этих определений).

Аналогичным образом, будем говорить, что НМТ принимает индивидуальную задачу распознавания, если существует такое допустимое вычисление (т.е. существует ветвь дерева), которое завершается состоянием q_y. При этом неважно, как ведут себя другие ветви: там может быть и состояние q_n, и бесконечные ветви.

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

Как это представить себе более наглядно? Предположим, имеется переборный алгоритм решения некоторой задачи. Представим себе НМТ, которая идет сразу по всем ветвям дерева перебора. Как только на одной из ветвей найден допустимый план – задача принята. Если все ветви завершились неудачей – задача не принимается.

Следующее важное определение. Говорят, что массовая задача распознавания принадлежит классу недетерминированно полиномиальных задач (Z Î NP), если существует такая НМТ, решающая эту задачу, время работы которой для всех принимаемых индивидуальных задач не превышает некоторого полинома P(l), где l = |z|.

Заметим: в определении ничего не говорится о непринимаемых задачах. Ничего не предполагается о степени P.

Что за задачи принадлежат классу NP? Их огромное количество. Во-первых, к ним относятся все полиномиальные задачи (P Í NP. поскольку детерминированная МТ – частный случай недетерминированной). Во-вторых, к классу NP относятся все полиномиально проверяемые задачи (ПП-задачи). Это вот что такое. Пусть каким-то образом получен план X (с неба, например, свалился). Если детерминированная МТ может за время не более P(l) проверить, является ли этот план допустимым, то данная задача является ПП-задачей. Нетрудно показать, что все ПП-задачи принадлежат NP.

Рассмотрим, например, задачу о коммивояжере в форме задачи распознавания (есть ли маршрут, длина которого не больше L?). Для нее неизвестен полиномиальный алгоритм решения, а вот проверить для заданного маршрута, превышает ли его длина величину L, не представляет труда. Аналогичным образом, нетрудно показать полиномиальную проверяемость задачи о рюкзаке, задачи о 8 ферзях и еще множества задач, хотя и не всех. Возьмем, например, шахматы: как по записи партии полиномиально проверить, что черные сопротивлялись наилучшим образом? Вряд ли это возможно.

Как было сказано выше, P Í NP. В настоящее время для множества задач из NP неизвестен полиномиальный алгоритм решения, однако не найдено ни одной NP-задачи, для которой было бы доказано, что полиномиальный алгоритм невозможен. Таким образом, остается открытым вопрос, имеет ли место равенство P = NP. Не исключено, что этот вопрос будет висеть вечно.

Имеет место еще один странный факт, трудно постигаемый рассудком программиста. Если некоторая задача распознавания Z Î NP, то не факт, что ее дополнение, т.е. задача с противоположным вопросом (~Z) тоже принадлежит NP. Казалось бы, решение задачи дает и решение ее дополнения: если в одном случае ответ «Да», то в другом – «Нет», и наоборот. Однако рассмотрим конкретный пример. На вопрос «Верно ли, что есть маршрут коммивояжера не длиннее 1000 км?» ответ «Да» может быть получен, если найден хоть один такой маршрут. Дополнительная же задача формулируется так: «Верно ли, что все возможные маршруты коммивояжера длиннее 1000 км?». Для ответа «Да» следует перебрать все эти маршруты. Если НМТ может за полиномиальное время найти один нужный маршрут, то из этого не следует, что она в состоянии за такое же время перебрать все. Не забывайте, что НМТ – это не реальное устройство, а математическая модель, и что в определении NP-задачи полиномиальное время требуется только для принимаемых задач, а не для отвергаемых.

2.4. NP-полные и NP-трудные задачи

Начнем с определений.

Задача Z называется NP-трудной, если любая другая задача Z' Î NP полиномиально сводима к задаче Z.

Задача Z называется NP-полной, если Z есть NP-трудная задача и Z Î NP.

Получается, что NP-полные задачи – как бы самые сложные задачи в классе NP: если для одной (любой) из этих задач будет найден полиномиальный алгоритм решения, то тогда любую NP-задачу можно будет решить за полиномиальное время. Для этого ее следует свести к соответствующей NP-полной задаче (за полиномиальное время!) и решить NP-полную задачу (тоже за полиномиальное время). Иначе говоря, если одна какая-нибудь NP-полная задача принадлежит классу P, то тогда классы P и NP полностью совпадают. Таким образом, отыскание хотя бы одного полиномиального алгоритма для какой-нибудь NP-полной задачи стало бы эпохальным событием в истории информатики. Никому не возбраняется попробовать свои силы.

Насколько реально доказать для какой-нибудь конкретной задачи, что она является NP-полной или NP-трудной? Кажется безнадежным делом доказывать полиномиальную сводимость всех NP-задач к одной конкретной. Отметим однако, что дело облегчается, если каким-то образом доказана NP-полнота хотя бы одной задачи. Пусть имеется одна доказанно NP-полная задача Z₁. Чтобы доказать NP-полноту задачи Z₂, достаточно сделать две вещи: во-первых, показать, что Z₂ Î NP (это обычно несложно), и во-вторых, суметь построить полиномиальное сведение Z₁ µ Z₂ (а не Z₂ µ Z₁, обратите внимание на направление!) Тогда получается, что любая NP-задача Z полиномиально сводится к Z₂ через Z₁. Теперь у нас есть уже две NP-полные задачи, Z₁ и Z₂, и для следующей задачи Z₃ можно уже выбирать, что легче доказать: Z₁ µ Z₃ или Z₂ µ Z₃. И так далее. В настоящее время известны сотни (если уже не тысячи) NP-полных и NP-трудных задач.

Отметим, что большая часть NP-полных задач – это задачи типа поиска («существует ли допустимый план?»). Для соответствующих задач оптимизации удается доказать NP-трудность, но далеко не всегда легко доказывается принадлежность классу NP.

Вообще, если Z – NP-полная задача, то для дополнительной задачи ~Z легко доказать NP-трудность, но мы видели выше, что принадлежность классу NP может и не иметь места.