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Р -полные задачи имеют псевдополиномиайные алгоритмы, которые достаточно эффективны на практике.

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