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может и не иметь места.