Примеры NP-полных задач: задача определения того, содержит ли неориентированный граф полный подграф





Напомним, что полный подграф неориентированного графа G=(V, E) – это граф G/=(V/, E/), для которого V/ Í V, E/ Í E, и между каждой парой вершин из E/ существует ребро в V/.

Для доказательства теоремы 2 используется теорема 1.

Теорема 1.Задача о выполнимости булевой формулы является NP-полной.

Теорема 2.Задача, определения того, содержит ли неориентированный граф G=(V, E) полный подграф с k вершинами, является NP-полной.

Доказательство.Опишем недетерминированный полиномиальный алгоритм для определения того, содержит ли G полный подграф с k вершинами. Алгоритм недетерминировано выбирает подмножество из k вершин и проверяет за время O(k2), является ли оно полным. Этим доказано, что задача входит в класс NP. Теперь мы должны доказать, что задача является NP-трудной; мы сделаем это показав, что в нее преобразуется задача выполнимости булевой формулы.

Предположим, что дано булево выражение С1 Ù С2 Ù … Ù Сk, представленное в конъюнктивной нормальной форме, где каждое Сi является дизъюнктом. Преобразуем вопрос о его выполнимости в вопрос существования полного подграфа с k вершинами в графе, который можно построить из данного выражения за время, полиномиальное относительно его длины. Рассмотрим неориентированный граф G=(V, E), определяемый следующим образом:

V={(a, i)| a - литерал в дизъюнкте Сi },

E={((a, i), (b, j))| i ¹ j и a ¹ b}.

Интуитивно ясно, что для каждого вхождения литерала в выражение графа G имеет вершину и ребра соединяют такие пары литералов из различных дизъюнктов, которым можно одновременно придать значение истинно. Полный подграф с k (число дизъюнктов) вершинами в G соответствует k литералам из разных дизъюнктов, которым одновременно можно придать значение истинно так, что литералы, дизъюнкты и отсюда само выражение имеют значение истинно. таким образом выражение является выполнимым, если G содержит полный подграф с k вершинами. Обратно, если выражение является выполнимым, то существует распределение значений истинно и ложно по переменным, такое, что выражение истинно. Иначе говоря, каждый из k дизъюнктов содержит литерал, значение которого есть истинно, и вершины, соответствующие этим буквам, образуют полный подграф с k вершинами. Таким образом, граф G=(V, E) содержит полный подграф с k вершинами, если и только если выражение является выполнимым. Очевидно, G можно построить по выражению за полиномиальное время.

Необычное свойство недетерминированных алгоритмов — различная сложность задачи разрешения и её дополнения. Практическое значение определения принадлежности задачи классу сложности

Рассмотрим задачи разрешения, ответами в которых являются просто «да» или «нет». Определим дополнение такой задачи Р как задачу , в которой ответы обратны.

Пример. Р: «Является ли данная булева формула выполнимой?»,

:«Является ли данная булева формула невыполнимой?»

Если существует детерминированный полиномиальный алгоритм для Р, то простым отрицанием выхода мы получаем детерминированный полиномиальный алгоритм для . Таким образом, РÎP тогда и только тогда, когда Î P. Для NP такой результат неизвестен, а именно: неизвестно, что существование недетерминированного полиномиального алгоритма для задачи Р гарантирует существование такого алгоритма для .

Тот факт, что задача разрешения и её дополнение могут быть неодинаковой сложности, противоречит нашему интуитивному представлению. Трудность здесь проистекает из необычной природы недетерминированного вычисления: ответ «да» должен соответствовать оператору успех и мы не можем просто взять дополнение к выходу недетерминированного алгоритма, поменяв местами успех и неудача, поскольку окончательный успех требует только одного успешного пути вычислений, в то время как окончательная неудача требует чтобы все пути вычисления вели к неудаче. Это означает, что недетерминированное вычисление более приспособлено для задачи существования типа «существует ли элемент х, такой, что некоторое свойство для него выполняется?», чем для дополнительных к ним задач несуществования типа «выполняется ли некоторое свойство для всех х?».

Доказано, что для любой NP-полной задачи P дополнение Î NP тогда и только тогда , когда класс NP замкнут относительно дополнения.

Понятие NP-полноты первоначально возникло в связи с попытками доказать гипотезу P ¹ NP. Если это так, то NP-полные задачи лежат в разности NP\ P. В настоящее время известно много примеров NP-полных задач, но ни про одну из них не удалось доказать, что она лежит в классе P. Сейчас характеризация задачи как NP-полной (NP-трудной) воспринимается как довод в пользу невозможности ее практического решения программными средствами в столь общей постановке, т.е. написать программу на всех исходных данных не удается. Выходом является сужение задачи, переход к частным случаям, на которых программа работает эффективно.

 





Читайте также:
Основные научные достижения Средневековья: Ситуация в средневековой науке стала меняться к лучшему с...
Методы лингвистического анализа: Как всякая наука, лингвистика имеет свои методы...
Продление сроков использования СИЗ: Согласно пункта 22 приказа Минздравсоцразвития России от...
Понятие о дефектах. Виды дефектов и их характеристика: В процессе эксплуатации автомобилей происходит...

Рекомендуемые страницы:



Вам нужно быстро и легко написать вашу работу? Тогда вам сюда...

Поиск по сайту

©2015-2021 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-02-12 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту:

Мы поможем в написании ваших работ! Мы поможем в написании ваших работ! Мы поможем в написании ваших работ!
Обратная связь
0.01 с.