На этом шаге мы рассмотрим классы сложности P, NP, NPI, NPC.
IF NP ≠ P then NP:= P∪NPC∪NPI
Введем еще один класс задач - NP-полные (NPC) задачи (проблемы). Проблема Т называется NP-полной, если она удовлетворяет двум условиям:
- Т ∈ NP,
- Если R ∈ NP, то R сводится к T за полиномиальное время.
NP-полные проблемы являются своего рода универсальными. Не нужно придумывать алгоритмы для других задач, достаточно свести эти задачи к какой-либо NP-полной проблеме и воспользоваться алгоритмом ее решения. Представим на секунду, что для какой-то NP-полной проблемы ... два программиста, работая в старом заброшенном гараже ... (так обычно начинаются байки про гениальных программистов и гениальные программы) написали алгоритм полиномиальной сложности. Это будет означать, что P = NP!
С тех пор как С.Кук доказал в 1971 г., что проблема выполнимости для пропозиционального исчисления является NP-полной, множество NPC пополнилось сотнями проблем.
NP-полные проблемы, как следует из определения, являются наиболее трудными в классе NP.
Значение класса NP-полных проблем состоит еще и в том, что ему принадлежат очень многие известные и важные в прикладном отношении задачи. Перечислим некоторые из них.
1. Задача изоморфизма подграфу.
Даны два графа G1 и G2. Множество вершин первого графа обозначим V1, а второго - V2. Пусть |V1|>|V2|=n. Требуется ответить на вопрос: найдется ли в графе G1 подграф Н, изоморфный графу G2?
2. Задача о клике.
Дан граф G с m вершинами и целое положительное число n. Граф называется кликой, если каждая вершина в нем связана ребром с каждой. Количество вершин в клике назовем ее мощностью. Верно ли, что в данном графе G имеется клика мощности не менее, чем n?
3. Гамильтонов цикл.
Дан граф G с n вершинами. Существует ли в графе простой цикл, проходящий через все вершины графа? Простым называется цикл, в котором вершины не повторяются. Таким образом, гамильтонов цикл - это последовательность вершин и дуг (ребер) графа, содержащая все вершины графа G по одному разу, но, может быть, содержащая не все дуги.
4. Задача коммивояжера.
Дан граф G с n вершинами. Каждому ребру графа приписано положительное целое число di, задающее длину ребра. Кроме этого, задано некоторое положительное целое число L. Требуется ответить на вопрос: найдется ли в графе G маршрут, проходящий через все вершины графа G такой, что его длина не превышает L?
Другие модификации задачи о коммивояжере требуют отыскания маршрута минимальной длины, гамильтонова цикла и т. п. Неизменным остается требование однократного прохождения через все вершины.
5. Вершинное покрытие.
Дан граф G с m вершинами и целое положительное число n. Вершинным покрытием называется подмножество U ⊆ V множества V вершин графа такое, что любое ребро графа G инцидентно хотя бы одной из вершин множества U (вторая вершина ребра может либо принадлежать, либо не принадлежать множеству U). Существует ли вершинное покрытие не более, чем из n вершин?
6. Разбиение.
Дано множество положительных целых чисел x1, x2, ..., xn. Можно ли разбить его на два подмножества так, чтобы суммы чисел в обоих подмножествах были равны?
7. Трехмерное сочетание.
Даны три множества: A, B, C. Мощности их равны: |А| = |В| = |С| = m, но множества не пересекаются. Зафиксировано некоторое множество троек N⊆A×B×C, |N|=n. Трехмерным сочетанием называется подмножество M⊆N, |M| = m, в котором ни какие две разных тройки не имеют ни одной равной координаты.
Кроме класса NP-полных проблем рассматривают еще и класс NP-трудных проблем.
Проблема Т называется NP-трудной, если она удовлетворяет условию: если R∈NP, то R сводится к T за полиномиальное время.
Заметим, что это условие совпадает со вторым условием для NP-полных проблем. Следовательно, NP-полная проблема - это NP-трудная задача, принадлежащая классу NP.
Для того чтобы уяснить себе возможное различие между классами P и NP, продолжим анализ проблемы выполнимости логического выражения.
Кроме общей задачи о выполнимости могут быть поставлены задачи с ограничивающими условиями. Например, ограничение на длину дизъюнктов.
На следующем шаге мы рассмотрим задачу о k-выполнимости.
