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

Вспомним определение обычной МТ. Имеется бесконечная лента, в ячейках которой записаны буквы из алфавита A = {a1, a2, ... am}, задано множество состояний машины Q = {q1, q2, ... qn} и множество правил перехода R = {qiaj q'ia'jdk}, где dk- сдвиг ленты, dk {L, R, E}. Задано начальное состояние и заключительное состояние q0. Слегка изменим это определение, введя два заключительных состояния qyи qn, соответствующих двум возможным ответам в задаче распознавания. Как говорилось выше, любая задача распознавания принадлежит либо классу 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-задачи полиномиальное время требуется только для принимаемых задач, а не для отвергаемых.