4.5. Список задач класса NP

В этот список попадают следующие задачи:

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

• Трехцветная раскраска графа.

• Построение клики из вершин на неориентированном графе.

• Покрытые множеств: пусть давно семейство подмножеств некоторого множества требуется найти подсемейство из такое, что

• Разбиение множества: то же условие, что и в предыдущем случае, но, кроме того, обязательно требуется (для всяких принадлежащих

Существование гамильтонова цикла на неориентированном графе.

• Задача о рюкзаке: для переменных принимающих значения 0 и 1, найти решение уравнения

В более общем виде это решение диофантова уравнения (т. е. уравнения в целых числах).

• Разбиение на две части: пусть дано чисел у,- из множества требуется разбить их на два непересекающихся подмножества таких, что

• Существование на ориентированном графе такого имеющего вид цикла маршрута коммивояжера, общая стоимость которого меньше заданного числа

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

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

(см. скан)

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

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

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

На первый взгляд такое положение не соответствует “интуиции”, поскольку в классе Р аналогичное утверждение является справедливым. Но перейти к дополнительной задаче в классе NP означает поменять местами в соответствующем недетерминированном алгоритме все случаи успехов и неудач. Для задачи конечный успех означает неудачу во всех ветвях исходного недетерминированного алгоритма. Следовательно, для получения ответа нужно подождать, пока закончат работу все Сложности суммируются, а поскольку число не обязательно полиномиально, ничто не обеспечивает того, чтобы при

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

Из задач на оптимизацию в класс NP попадает только задача поиска существования решения с заданной стоимостью. В общем случае задача оптимизации в настоящее время не может быть отнесена к какому-либо классу.