Составители:
Рубрика:
5.4. Труднорешаемые задачи
NP-полная задача П называется универсальной, если к ней
полиномиально сводится любая NP-полная задача. Выше была
доказана принадлежность задачи выполнимости к.н.ф. к классу NP-
полных задач.
Приведем другие примеры задач этого класса: о полном
подграфе, о вершинном покрытии, о сложности д.н.ф. частичной
булевой функции и о трехмерном сочетании.
Задача о полном подграфе. Граф называется полным, если
любые две его вершины соединены ребром. По заданному
неориентированному графу G и числу k требуется определить,
имеется ли в G полный подграф с k вершинами.
Задача о вершинном покрытии. Некоторое подмножество V
′
,
содержащее k=⎮V
′
⎮ вершин, образует вершинное покрытие
мощности k графа G, если для любого ребра найдется инцидентная
ему вершина в подмножестве V
′
.
По заданному графу G и числу k требуется определить, имеет
ли G вершинное покрытие мощности k.
Задача о сложности д.н.ф. частичной булевой функции. По
частичной булевой функции f и числу k необходимо установить,
возможно ли построить д.н.ф. для f, содержащую не более k букв.
Трехмерное сочетание. Дано множество M⊆W×X×Y, где W,X,Y
– непересекающиеся множества, содержащие одинаковое число
элементов q. Необходимо установить, что M содержит трехмерное
сочетание, т.е. подмножество M
′
⊆M такое, что⎮M
′
⎮=q и никакие два
разных элемента M
′
не имеют ни одной равной координаты.
Например, W={a,b,c}, X={d,e,f}, Y={j,h,i} и M = {(a,d,i), (a,e,i),
(a,f,j), (b,e,i), (b,f,j), (c,e,h), (c,d,i)}. Данный пример имеет
положительное решение: M
′
={(a,d,i), (b,f,j), (c,e,h)}⊆M.
– задача о выполнимости к.н.ф. Тогда, чтобы доказать,
Пусть П
1
179
Страницы
- « первая
- ‹ предыдущая
- …
- 93
- 94
- 95
- 96
- 97
- …
- следующая ›
- последняя »
