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

NP — это аббревиатура для «недетерминированный полиномиальный». Рассмотрим понятие недетерминированного алгоритма. Для задачи коммивояжера детерминированный алгоритм, например, поиск с возвращением, определяет, по какой дуге следует направляться из текущего узла. Для задачи распознавания, существует ли в графе цикл, длины меньшей B, поиск с возвращением неявно перебирает все циклы и дает ответ «да», если такой цикл существует, и «нет» в противном случае.

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

Недетерминированный алгоритм может правильно угадать, какая дуга из текущей вершины должна быть следующей. Итак, если существует цикл общей длины, меньшей В, то недетерминированный алгоритм тратит время О (п)на вычисление суммарной длины и проверки того, меньше ли она чем В. Таким образом, если ответ «да», то задача коммивояжера с помощью недетерминированного алгоритма может быть решена за полиномиальное время.

Грубо говоря, если ответ «да» можно проверить за полиномиальное время, то задачу можно решить недетерминированным алгоритмом за полиномиальное время и задача принадлежит классу NP.

С другой стороны, если цикла длины меньшей В в графе не существует, то для ответа «нет», по-видимому, не достаточно уметь правильно угадывать нужную дугу. Таким образом, задача с ответом «нет», вероятно, не принадлежит классу NP.

Если некоторая задача принадлежит классу Р, то дополнение к ней также принадлежит Р. Скорее всего, аналогичное утверждение не верно для класса NP (хотя это и не доказано).

По определению, если задача принадлежит Р, то она принадлежит NP. Итак, класс Р является подклассом класса NP т.e. Р NP. Основной вопрос современной теории сложности — это

P = NP?

Для доказательства Р = NP достаточно показать, что для решения всякой задачи из NP существует полиномиальный детерминированный алгоритм. Никто еще не сделал этого. Для доказательства Р NP достаточно показать, что в NP есть задача, которую детерминированным алгоритмом нельзя решить за полиномиальное время. Никто еще не сделал и этого. Большинство исследователей полагает, что Р NP.