Другие МР-полные проблемы
Между тем для многих проблем доказано, что они являются NP - полными. Если бы для одной из этих проблем удалось найти полиномиальный детерминированный алгоритм, то было бы также доказано, что NP = Р. Показательными примерами таких проблем являются следующие.
1. Клика. Пусть задан неориентированный граф множеством V вершин, симметричным отношением R Í V x V для ребер и задано число k Î N. Ищется ответ на вопрос: существует ли подмножество С Î V, такое, что ôcô = k и С х С Í R?
2. Целочисленное программирование. Пусть даны матрица А Î Z^nxn и целочисленный вектор v Î Z^n. Ищется вектор с Î {0, 1}” с Ас > v (поэлементно).
3. Перекрывающееся множество вершин. Пусть заданы неориентированный граф множеством вершин V и R Í V x V c R== R^T, а также число k Î N. Ищется множество вершин U Í V с ÷Uç == k, такое, что имеет место:
v, w Î V: (v, w) Î R Þ Ø(v Î U Û w Î U).
Формулируя словами, ищется часть множества вершин U, такая, что каждое ребро имеет вершину в U и вершину вне U.
4. Направленный круг Гамильтона. Дан ориентированный граф с множеством вершин V и R Í V x V. Ищется замкнутая трасса (обход), в которой каждая вершина встречается ровно один раз. Эта проблема является NP-полной также и для неориентированного графа.
5. Задача коммивояжера. Задано множество вершин V == {1, ..., n}, функция расстояний
dist:V^2 ® N
и число k Î N. При этом пусть для функции расстояния dist справедливо неравенство треугольника
" i, j, 1: dist(i, 1)+dist(1, j) ³ dist(i, j).
Ищется перестановка (Xi, ..., Хn) вершин в V (путь поездки) с п-1
S dist(Xi, Xi+i)+dist(Xn, x1) ³ k. I=1
Следующие родственные постановки задач для большинства перечисленных проблем имеют такую же сложность: установить, существует ли решение проблемы Р;
· найти решение проблемы Р.
Установление того, существует ли решение, часто бывает возможным только конструктивным путем, через построение (неявное) решения. Кроме того, для многих из этих проблем типично, что с очень -небольшими затратами времени можно проверить, дает ли фактически решение предлагаемый способ.
Типичным методом доказательства NP-полноты постановки задачи Х является ее сведение за полиномиальное время к какой-либо задаче, для которой NP-полнота доказана.
