Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 105
Текст из файла (страница 105)
Построение, очевидно, требует времени, которое линейно зависит от длины Е, так как ни в одном из рассмотренных выше четырех случаев длина дизъюнкта не увеличивается более, чем в 3213 раза (соотношение числа символов в случае!). Кроме того, символы, необходимые для построения формулы Е, легко найти за время, пропорциональное числу этих символов. Поскольку проблема ВКНФ ХР-полна, то и проблема ЗВЫП также ХР-полна. ьЗ 10.3.5. Упражнения к разделу 10.3 10.3.1. Приведите следующие формулы к 3-КНФ: а) (г)хужйх б) ихув4 и -';ж в) иху'- хим ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ 450 10.3.2. Проблема 4П-ВЫП определяется следующим образом: по данной булевой формуле Е выяснить, есть ли у нее хотя бы четыре удовлетворяющие подстановки. Покажите, что проблема 4П-ВЫП Нр-полна.
10.3.3. В этом упражнении определяется семейство 3-КНФ-формул. Формула Е„имеет л переменных х„х„..., х„. Для всякого множества из трех различных целых чисел от 1 до и формула Е„содержит дизъюнкты (х, + х~ -ьх,) и (х ~ -ь х з + х з). Выполнима ли Е„для: а) (в!) и= 4? б) (1!) и= 5? 103.4. (!)Постройте алгоритм с полиномиальным временем работы для решения проблемы 2ВЫП (2-выполнимости), т.е, проблемы выполнимости булевой формулы в КНФ, каждый дизъюнкт которой содержит ровно два литерала.
Указание. Если один из двух литералов в дизъюнкте ложен, то второй обязательно истинеи. Сделайте вначале предположение относительно истинности одной из переменных, а затем постарайтесь извлечь все возможные следствия для оставшихся переменных. 10.4. Еще несколько ХР-полных проблем Приведем несколько примеров того, как с помощью одной )чР-полной проблемы кожно доказать МР-полноту целого ряда других.
Этот процесс получения новых НР- полных проблем имеет два важных следствия. ° Обнаружив новую НР-полную проблему, мы не получаем практически никаких шансов на отыскание эффективного алгоритма ее решения. Мы стремимся найти эвристики, частные решения, аппроксимации, применяем какие-либо иные методы, лишь бы избежать решения "в лоб". Более того, мы можем делать все это, будучи уверенными, что не просто "не замечаем метод".
° Всякое добавление новой проблемы Р в список )4Р-полных проблем дает еще одно подтверждение гипотезы, что все они требуют экспоненциального времени. Усилия, затраченные на поиски полиномиального алгоритма решения проблемы Р, мы, сами того не зная, посвятили обоснованию равенства Р = МР. Именно безуспешные попытки многих первоклассных математиков и других ученых доказать нечто эквивалентное утверждению Р = МР в конечном счете убеждают в том, что это равенство невероятно и, наоборот, все ХР-полные проблемы требуют экспоненциального времени, В этом разделе мы встретим несколько !4Р-полных проблем, связанных с графами. Эти проблемы чаще других используются при решении практических вопросов. Мы по- 10.4.
ЕЩЕ НЕСКОЛЬКО гчР-ПОЛНЫХ ПРОБЛЕМ 457 говорим о проблеме коммивояжера (ИКОМ), с которой уже встречались в разделе 10.1.4. Покажем, что более простая, но также важная версия этой проблемы, называемая проблемой гамильтонова цикла (ГЦ),14Р-полна. Тем самым покажем, что ХР-полной является и более общая проблема ПКОМ. Представим несколько проблем, касающихся "покрытия'* графов, таких, как "проблема узельного покрытия". В ней требуется отыскать наименьшее множество узлов, "покрывающих" все ребра так, чтобы хотя бы один конец каждого ребра принадлежал выбранному множеству.
10.4.1. Описание ХР-полных проблем Вводя новую ХР-полную проблему, будем использова~ь следующую стилизованную форму ее определения. 1. Назвоние проблемы и, как правило, его аббревиатура, например, ВЫП или ПКОМ. 2. Вход проблемы; что и каким образом представляют входные данные. 3. Искомый выход; при каких условиях выходом будет "да". 4. Проблема, сведение которой к данной доказывает ХР-полноту последней. Пример 10.16. Вот как могут выглядеть описание проблемы 3-выполнимости и доказательство ее ХР-полноты. Проблема. Выполнимость формул, находящихся в 3-КНФ (ЗВЫП). Вход. Булева формула в 3-КНФ. Выход. Ответ "да" тогда и только тогда, когда формула выполнима.
Проблема, сводящаяся к данной. ВКНФ. П 10.4.2. Проблема независимого множества Пусть Π— неориентированный граф. Подмножество 1 узлов С называется независимым яшожеством, если никакие два узла из 1 не соединены между собой ребром из О. Независимое множество является максииальным, если оно не меньше (содержит не меньше узлов), чем любое независимое множество этого графа. Пример 10.17. Для графа, изображенного на рис. 10.1 (см. раздел 10.1.2), максимальным независимым множеством является (1,4). Это единственное множество размера два, которое является независимым, поскольку для любых других двух узлов существует соединяющее их ребро.
Таким образом, никакое множество размера три и более не является независимым, например. множество (1, 2, 4) (есть ребро между узлами 1 и 2). Итак, (1, 4) — максимальное независимое множество, причем единственное для данного графа, хотя граф может иметь много максимальных независимых множеств. Например, множество (1) также независимо для данного графа, но не максимально. П В комбинаторной' оптимизации проблема максимального независимого множества обычно формулируется так: для данного графа найти максимальное независимое множество.
Но, как и любую проблему в теории сложности, мы должны сформулировать ее в ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ 488 терминах ответа "да*' или "нет'*. Поэтому в формулировку проблемы нам придется ввести нижнюю границу и сформулировать проблему как вопрос о том, существует ли для данного графа независимое множество размера, не меньшего атой нижней границы.
Формальное определение проблемы максимального независимого множества имеет следующий вид. Проблема. Независимое множество (НМ). Вход. Граф С и нижняя ераница й, значение которой заключено между 1 и числом узлов С. Выход. Ответ "да" тогда и только тогда, когда С имеет независимое множество из lс узлов. Проблема, сводящаиси к данной. Проблема ЗВЫП. Мы должны, как и пообещали, доказать НР-полноту проблемы НМ, сведя к ней проблему 3ВЫП. Теорема 10.18. Проблема независимого множества НР-полна. Доказательство.
Легко видеть, что проблема НМ принадлежит классу МР. Для данного графа С нужно у~адать набор из !сего узлов и проверить их независимость. Теперь опишем сведение ЗВЫП к НМ. Пусть Е = (ее)(ел) ... (е„) — формула в З-КНФ. По Е строится граф С, содержащий Зт узлов, которые обозначим как [й А, где 1< ! < лп, а ! = 1, 2 или 3. Узел [ЪЯ представляет зцй литерал в дизъюнкте ен На рис.10.8 приведен пример графа С, пос~роенного по 3-КНФ (лен х н хл)( л~ н х хл)( х '~' хе ! хл)( хз "н хд н" хе ) Рис.
! 08. Построение нелависи ного мноэнесмва по выполним~ой булевой фориуле, наладив!ейсл в 3-КИФ 10.4, ЕЗЦЕ НЕСКОЛЬКО 1н1Р-ПОЛНЫХ ПРОБЛЕМ 459 Дизъюнкты формулы представлены столбцами. Поясним вкратце, почему узлы имеют именно такой вил. "Фокус" построения О' состоит в том, чтобы каждое независимое множество из т узлов представляло один из способов выполнить формулу Е. Ключевых идей тут две. 1. Мы хотим гарантировать, что можно выбрать только один узел, соответствующий данному дизьюнкту. Для этого помешаем ребра между каждой парой узлов из одного столбца„т.е. создаем ребра ([г', 1], [б 2]), ([б 1], [б 3]) и ([г', 2], [1, 3]) для всех 1 (см, рис.
10.8), 2. Нам необходимо предотвратить выбор в качестве элементов независимого множества таких узлов, которые представляют литералы, дополняющие друг друга. Поэтому, если есть два узла [1ь)Д и [1л/э], один из которых представляет переменную х, а второй — х, то соединяем их ребром. Таким образом, их нельзя одновременно выбрать в качестве элементов независимого множества. Граница к для графа О, построенного по этим двум правилам, равняется т. Легче ли проблемы, требующие ответа "да" или "иет*"? Может показаться, что "да~нет"-версия проблемы легче, чем исходная проблема оптимизации. Например, найти наибольшее независимое множество сложно, в то время как для данного небольшого значения границы й легко проверить, что существует независимое множество размера Е Однако, возможно, нам дана константа х, представляющая собой максимальный размер, для которого существует независимое множество.
Тогда лля решения "да/нет*'-версии проблемы необходимо найти максимальное независимое множество. В действизельности, все обычные ХР-полные проблемы оптимизации и их "да~нет"- версии имеют эквивалентную сложность, по крайней мере, в пределах полиномиальной зависимости. Например, если бы у нас был полиномиальный алгоритм, позволяющий войти максимальное независимое множество, то можно было бы решить "да/нет"-проблему, найдя максимальное независимое множество и проверив, что его размер не меньше предельного значения Е Поскольку, как мы покажем, "дЫнет"- версия Хр-полна, то и версия оптимизации должна быть трудно разрешимой. Сравнение можно провести и по-другому.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
