NP-полные задачи

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

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

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

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

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

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

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

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

P = NP?

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

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

Пусть каждая дуга графа имеет длину 1, а расстояние между двумя несмежными вершинами равно ∞. Так как в графе n вершин, то существование цикла длины п эквивалентно существованию гамильтонова цикла.

Заметим, что данное сведение требует полиномиального времени, а именно, на определение расстояний между n(n - 1)/2 парами вершин. Если нам удастся построить полиномиальный алгоритм для решения задачи коммивояжера, то тем самым мы найдем полиномиальный алгоритм для задачи о гамильтоновом цикле.

Будем говорить, что задача L₁ сводится к задаче L₂, и записывать L₁ L₂, если любой алгоритм для L₂ можно использовать для решения задачи L₁. Подразумевается, что это сведение тратит полиномиальное время. Если L₂ также можно свести к L_1; то говорят, что задачи L₁и L₂ полиноминально эквивалентны и пишут L₁ L₂,.

Оба отношения и транзитивны..

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

Задачи из этого подмножества называются NР-полными. Итак, класс NР содержит два интересных подкласса: подкласс задач, которые могут быть решены за полиномиальное время детерминированным алгоритмами и наиболее сложных в классе NР это символически изображено на рис. 37.

Рис. 37. Схематическое представление класса NP‑задач

Чтобы доказать, что Р = NP, достаточно для какой-нибудь NP полной задачи найти полиномиальный детерминированный алгоритм.

Чтобы показать, что РNР, достаточно для какой-нибудь задачи из NP установить что она не принадлежит классу Р.

Теорема (1971). Если некоторая NP-полная задача разрешима за полиномиальное время, то P=NP. Другими словами, если в классе NP существует задача, не разрешаемая за полиномиальное время, то все NP-полные задачи таковы.

Большинство исследователей полагает, что верна следующая гипотеза.

Гипотеза: РNP. Означает, что NP-полные задачи не могут быть решены за полиномиальное время.

Если мы найдем новую NP-полную задачу L, то есть небольшой шанс изобрести для нее полиномиальный алгоритм. Чтобы доказать, что задача L является NP-полной, достаточно доказать следующие два утвержденя:

(1) Задача L принадлежит классу NР.

(2) Известная NP-полная задача сводится к L.

• Рассмотрим три стандартные NР-полные задачи и их варианты.

1. Задача о разбиении. Существует ли в заданном числовом множестве х₁, х₂,.., х_n подмножество мощности k, такое, что сумма чисел в подмножестве равна В? Более общий вариант этой задачи —задача о рюкзаке.

2. Гамильтоновы циклы. Более общий вариант этой задачи — задача коммивояжера.

За. Задача о минимальном вершинном покрытии. Во множестве вершин V заданного графа G = (V, E) найти подмножество V’ V минимальной мощности, такое, что каждое ребро графа инцидентно по крайней мере одной вершине из V.

Существует другой, по существу, эквивалентный, вариант задачи За:

Зб. Задача о максимальном независимом множестве. Во множестве вершин V заданного графа G = (V, E) найти подмножество V" V максимальной мощности, такое, что никакое ребро графа не инцидентно двум вершинам из V". Можно проверить, что V" =V – V’. Например, подмножество вершин на рис. 8.2, помеченных а, является минимальным вершинным покрытием, а подмножество вершин, помеченных , образует максимальное независимое множество.

Алгоритмы, полиномиальные при ограниченной величине коэффициентов (входной информации, например, для задач о загрузке рюкзака это размер рюкзака и количества предметов) называются псевдополиномиальными. Многие NР-полные задачи имеют псевдополиномиайные алгоритмы, которые достаточно эффективны на практике.

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