Конспект установочных лекций по комплексному курсу Информатика, Теория информации


Другие МР-полные проблемы


Между тем для многих проблем доказано, что они являются 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-полнота доказана.

 




Начало  Назад  Вперед



Книжный магазин