dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 103
Текст из файла (страница 103)
Поскольку проблема ВКНФ NP-полна, то и проблема3ВЫП также NP-полна. 6Для удобства, говоря о литералах, считаем их переменными без отрицания, например x. Новсе наши построения остаются в силе и в том случае, когда некоторые или все литералы являютсяотрицаниями переменных, например x .456Стр. 456ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛ10.3.5. Óïðàæíåíèÿ ê ðàçäåëó 10.310.3.1. Приведите следующие формулы к 3-КНФ:а) (∗) xy + x z;б) wxyz + u + v;в) wxy + x uv.10.3.2. Проблема 4П-ВЫП определяется следующим образом: по данной булевой формуле E выяснить, есть ли у нее хотя бы четыре удовлетворяющие подстановки.Покажите, что проблема 4П-ВЫП NP-полна.10.3.3.
В этом упражнении определяется семейство 3-КНФ-формул. Формула En имеетn переменных x1, x2, …, xn. Для всякого множества из трех различных целых чисел от 1 до n формула En содержит дизъюнкты (x1 + x2 + x3) и ( x 1 + x 2 + x 3).Выполнима ли En для:а) (∗!) n = 4?б) (!!) n = 5?10.3.4. (!) Постройте алгоритм с полиномиальным временем работы для решенияпроблемы 2ВЫП (2-выполнимости), т.е. проблемы выполнимости булевойформулы в КНФ, каждый дизъюнкт которой содержит ровно два литерала.Указание.
Если один из двух литералов в дизъюнкте ложен, то второй обязательно истинен. Сделайте вначале предположение относительно истинностиодной из переменных, а затем постарайтесь извлечь все возможные следствиядля оставшихся переменных.10.4. Åùå íåñêîëüêî NP-ïîëíûõ ïðîáëåìПриведем несколько примеров того, как с помощью одной NP-полной проблемыможно доказать NP-полноту целого ряда других.
Этот процесс получения новых NPполных проблем имеет два важных следствия.• Обнаружив новую NP-полную проблему, мы не получаем практически никакихшансов на отыскание эффективного алгоритма ее решения. Мы стремимся найтиэвристики, частные решения, аппроксимации, применяем какие-либо иные методы, лишь бы избежать решения “в лоб”. Более того, мы можем делать все это,будучи уверенными, что не просто “не замечаем метод”.• Всякое добавление новой проблемы P в список NP-полных проблем дает ещеодно подтверждение гипотезы, что все они требуют экспоненциального времени. Усилия, затраченные на поиски полиномиального алгоритма решения проблемы P, мы, сами того не зная, посвятили обоснованию равенства P = NP.10.4.
ÅÙÅ ÍÅÑÊÎËÜÊÎ NP-ÏÎËÍÛÕ ÏÐÎÁËÅÌСтр. 457457Именно безуспешные попытки многих первоклассных математиков и другихученых доказать нечто эквивалентное утверждению P = NP в конечном счетеубеждают в том, что это равенство невероятно и, наоборот, все NP-полныепроблемы требуют экспоненциального времени.В этом разделе мы встретим несколько NP-полных проблем, связанных с графами.Эти проблемы чаще других используются при решении практических вопросов. Мы поговорим о проблеме коммивояжера (ПКОМ), с которой уже встречались в разделе 10.1.4.Покажем, что более простая, но также важная версия этой проблемы, называемая проблемой гамильтонова цикла (ГЦ), NP-полна.
Тем самым покажем, что NP-полной является и более общая проблема ПКОМ. Представим несколько проблем, касающихся“покрытия” графов, таких, как “проблема узельного покрытия”. В ней требуется отыскать наименьшее множество узлов, “покрывающих” все ребра так, чтобы хотя бы одинконец каждого ребра принадлежал выбранному множеству.10.4.1. Îïèñàíèå NP-ïîëíûõ ïðîáëåìВводя новую NP-полную проблему, будем использовать следующую стилизованнуюформу ее определения.1.Название проблемы и, как правило, его аббревиатура, например, ВЫП или ПКОМ.2.Вход проблемы: что и каким образом представляют входные данные.3.Искомый выход: при каких условиях выходом будет “да”.4.Проблема, сведение которой к данной доказывает NP-полноту последней.Пример 10.16.
Вот как могут выглядеть описание проблемы 3-выполнимости и доказательство ее NP-полноты.Проблема. Выполнимость формул, находящихся в 3-КНФ (3ВЫП).Вход. Булева формула в 3-КНФ.Выход. Ответ “да” тогда и только тогда, когда формула выполнима.Проблема, сводящаяся к данной.
ВКНФ. 10.4.2. Ïðîáëåìà íåçàâèñèìîãî ìíîæåñòâàПусть G — неориентированный граф. Подмножество I узлов G называется независимым множеством, если никакие два узла из I не соединены между собой ребром из G.Независимое множество является максимальным, если оно не меньше (содержит неменьше узлов), чем любое независимое множество этого графа.Пример 10.17.
Для графа, изображенного на рис. 10.1 (см. раздел 10.1.2), максимальным независимым множеством является {1, 4}. Это единственное множество размерадва, которое является независимым, поскольку для любых других двух узлов существуетсоединяющее их ребро. Таким образом, никакое множество размера три и более не является независимым, например, множество {1, 2, 4} (есть ребро между узлами 1 и 2). Итак,458Стр.
458ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛ{1, 4} — максимальное независимое множество, причем единственное для данного графа, хотя граф может иметь много максимальных независимых множеств. Например,множество {1} также независимо для данного графа, но не максимально.
В комбинаторной оптимизации проблема максимального независимого множестваобычно формулируется так: для данного графа найти максимальное независимое множество. Но, как и любую проблему в теории сложности, мы должны сформулировать ее втерминах ответа “да” или “нет”. Поэтому в формулировку проблемы нам придется ввести нижнюю границу и сформулировать проблему как вопрос о том, существует ли дляданного графа независимое множество размера, не меньшего этой нижней границы.Формальное определение проблемы максимального независимого множества имеет следующий вид.Проблема. Независимое множество (НМ).Вход.
Граф G и нижняя граница k, значение которой заключено между 1 и числом узлов G.Выход. Ответ “да” тогда и только тогда, когда G имеет независимое множество изk узлов.Проблема, сводящаяся к данной. Проблема 3ВЫП.Мы должны, как и пообещали, доказать NP-полноту проблемы НМ, сведя к ней проблему 3ВЫП.Теорема 10.18. Проблема независимого множества NP-полна.Доказательство.
Легко видеть, что проблема НМ принадлежит классу NP. Для данного графа G нужно угадать набор из k его узлов и проверить их независимость.Теперь опишем сведение 3ВЫП к НМ. Пусть E = (e1)(e2) … (em) — формула в 3-КНФ.По E строится граф G, содержащий 3m узлов, которые обозначим как [i, j], где 1≤ i ≤ m, аj = 1, 2 или 3. Узел [i, j] представляет j-й литерал в дизъюнкте ei. На рис.10.8 приведенпример графа G, построенного по 3-КНФ(x1+ x2 + x3)( x1 + x2 + x4)( x2 + x3+x5)( x3 + x4 + x5 ).Дизъюнкты формулы представлены столбцами.
Поясним вкратце, почему узлы имеютименно такой вид.“Фокус” построения G состоит в том, чтобы каждое независимое множество из m узлов представляло один из способов выполнить формулу E. Ключевых идей тут две.1.Мы хотим гарантировать, что можно выбрать только один узел, соответствующийданному дизъюнкту. Для этого помещаем ребра между каждой парой узлов из одного столбца, т.е. создаем ребра ([i, 1], [i, 2]), ([i, 1], [i, 3]) и ([i, 2], [i, 3]) для всех i(см. рис. 10.8).2.Нам необходимо предотвратить выбор в качестве элементов независимого множества таких узлов, которые представляют литералы, дополняющие друг друга.
Поэтому,если есть два узла [i1, j1] и [i2, j2], один из которых представляет переменную x, а10.4. ÅÙÅ ÍÅÑÊÎËÜÊÎ NP-ÏÎËÍÛÕ ÏÐÎÁËÅÌСтр. 459459второй — x , то соединяем их ребром. Таким образом, их нельзя одновременно выбрать в качестве элементов независимого множества.Граница k для графа G, построенного по этим двум правилам, равняется m.Рис. 10.8. Построение независимого множества по выполнимойбулевой формуле, находящейся в 3-КНФËåã÷å ëè ïðîáëåìû, òðåáóþùèå îòâåòà “äà” èëè “íåò”?Может показаться, что “да/нет”-версия проблемы легче, чем исходная проблема оптимизации.
Например, найти наибольшее независимое множество сложно, в то времякак для данного небольшого значения границы k легко проверить, что существует независимое множество размера k. Однако, возможно, нам дана константа k, представляющая собой максимальный размер, для которого существует независимое множество. Тогда для решения “да/нет”-версии проблемы необходимо найти максимальноенезависимое множество.В действительности, все обычные NP-полные проблемы оптимизации и их “да/нет”версии имеют эквивалентную сложность, по крайней мере, в пределах полиномиальной зависимости. Например, если бы у нас был полиномиальный алгоритм, позволяющий найти максимальное независимое множество, то можно было бы решить“да/нет”-проблему, найдя максимальное независимое множество и проверив, что егоразмер не меньше предельного значения k.
Поскольку, как мы покажем, “да/нет”версия NP-полна, то и версия оптимизации должна быть трудно разрешимой.460Стр. 460ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛСравнение можно провести и по-другому. Предположим, что у нас есть полиномиальный алгоритм решения “да/нет”-проблемы НМ. Если граф имеет n узлов, то размер максимального независимого множества заключен между 1 и n. Прогоняя алгоритм решения НМ для всех возможных значений границы от 1 до n, мы, безусловно,найдем размер максимального независимого множества (но не обязательно само этомножество) за время, необходимое для однократного решения НМ и умноженное наn.
В действительности, с использованием бинарного поиска нам будет достаточновремени однократного решения, умноженного всего лишь на log2 n.Граф G и границу k можно построить по формуле E за время, пропорциональноеквадрату длины E, поэтому преобразование E в G представляет собой полиномиальноесведение. Мы должны показать, что оно корректно сводит 3ВЫП к проблеме НМ, т.е.• E выполнима тогда и только тогда, когда G имеет независимое множестворазмера m.(Достаточность) Во-первых, заметим, что независимое множество не может содержать два узла из одного и того же дизъюнкта, [i, j1] и [i, j2], где j1 ≠ j2, поскольку все такие узлы попарно соединены ребрами, как в столбцах на рис. 10.8. Поэтому, если существует независимое множество размера m, то оно содержит только по одному узлу из каждого дизъюнкта.Более того, независимое множество не может одновременно содержать узлы, которыесоответствуют некоторой переменной x и ее отрицанию x , поскольку такие узлы попарно соединены ребрами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
