4.4. Класс NP: недетерминированные полиномиальные задачи

4.4.1. Два семейства машин

Когда для решения задачи мы не располагаем ни явной формулой, ни рекурсивным выражением приемлемой сложности, нам остается два последних способа: построение действенного алгоритма подсчета или метод перебора. Если мы говорим, что сложность задачи полиномиальна, это означает, что в любом случае, не прибегая к перебору, мы достигнем решения за полиномиальное число шагов.

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

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

Помимо обычного набора инструкций в такой машине существует специальная инструкция которая создает столько копий текущего состояния, сколько существует элементов во множестве Е. По соглашению машина останавливается в тот момент, когда одна из возникших ее копий достигает инструкции

Опишем на этом новом языке недетерминированные алгоритмы для двух простых задач.

Задача 1. Разрешимость логического выражения

Пусть дано логическое выражение Е. Оно включает символы и логические переменные Нам нужно так подобрать значения чтобы при этих значениях выражение было ИСТИННЫМ. Например, если

то подойдет множество (ЛОЖЬ, ИСТИНА, ЛОЖЬ, ЛОЖЬ).

Алгоритм для НДМТ запишется в следующем виде:

(см. скан)

Итак, этот алгоритм создает копий самого себя, и, в частности, двенадцатая копия приводит к успеху. В таком случае выражение Е называется разрешимым.

Задача 2. Раскраска географической карты в 3 цвета.

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

Недетерминированный алгоритм:

(см. скан)

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

экспоненциально по природе, очень быстро происходит “взрыв” (см. два предыдущих случая).

Замечание 1. В предыдущих случаях каждая отдельная копия является детерминированной, а число шагов — следовательно, и сложность каждой копии — полиномиально (в двух предыдущих случаях оно фактически линейно). Если обобщить сказанное выше, всякий алгоритм, который может быть выполнен за полиномиальное время на недетерминированной машине Тьюринга, мы будем называть недетерминированным полиномиальным алгоритмом, или сокращенно Следствие, которое непосредственно вытекает из этого определения, можно записать в виде

т. е. множество задач, полиномиальных на входит в поскольку является частным случаем НДМТ.

Замечание 2. Для того чтобы перейти из NP в Р, нужно “совсем немного”. Так, во второй задаче, если мы допускаем только два цвета, предыдущий алгоритм дает ответ (возможно или невозможно), не используя ту петлю, в которой фигурирует ключевая инструкция “ВЫБОР”. Вывод о характере ответа достигается за шагов без какого бы то ни было возвращения назад: НДМТ сводится к . В первой задаче множество возможных значений с самого начала ограничено двумя элементами. Однако в этом случае простота вычисления зависит от числа логических переменных внутри одной пары скобок. В самом деле, предположим, что их число не более двух и подлежащее оценке выражение приведено к нормальному виду

где обозначают либо либо Поэтому, когда мы фиксируем значение первого терма, например в данной паре скобок — о, эта пара скобок может сразу принять значение ИСТИНА, и тогда мы перейдем к паре. Если получить решение на первом же шаге не удалось, вид второго терма, т. е. позволяет сразу, т. е. не прибегая к инструкции “ВЫБОР”, а исходя из условия, получить то значение, которое должна принять эта соседняя переменная. Если вплоть до данный процесс распространения ограничений проходит успешно, алгоритм сразу выдаст ответ в виде вектора в противном случае рассматриваемое выражение неразрешимо.

Итак, граница между классами Р и NP является резкой, причем проходит она по очень близким значениям;

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

и или.

В настоящее время ответа на этот вопрос пока нет.