Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 234
Текст из файла (страница 234)
34.4-2. Приведите 3-СХР формулу, которая получится в результате применения метода, описанного в теореме 34.10, к формуле (34.3). 34.4-3. Профессор предложил показать, что Злт <г 3-СХГ Блт, лишь с помощью метода с использованием таблицы истинности, описанного в до- Глава 34. ХР-полнота 1127 казательстве теоремы 34.10, исключая при этом другие этапы. Другими словами, профессор предложил взять булеву формулу ф, составить таблицу истинности для ее переменных, получить из нее формулу в З-ПХР, эквивалентную ~ф, после чего составить логическое отрицание полученной формулы и с помощью законов де Моргана получить 3-СХР формулу, эквивалентную формуле ф.
Покажите, что в результате применения такой стратегии не удается выполнить приведение формулы в течение полиномиального времени. 34.4-4. Покажите, что задача определения того, является ли тавтологией данная формула, является полной в классе со-ХР. (Указание: см. упражнение 34.3-7). 34.4-5. Покажите, что задача по определению выполнимости булевых формул в дизъюнктивной нормальной форме разрешима в течение полиномиального времени.
34.4-6. Предположим, кто-то разработал алгоритм с полиномиальным временем выполнения, позволяющий решить задачу о выполнимости формул. Опишите, как с помощью этого алгоритма в течение полиномиального времени находить выполняющие наборы. 34.4-7. Пусть 2-СХР БАт — множество выполнимых булевых формул в СХР, у которых каждое подвыражение в скобках содержит ровно по два литерала. Покажите, что 2-СХЕ Блт е Р. Постарайтесь, чтобы ваш алгоритм был как можно более эффективен. (Указание: воспользуйтесь тем, что выражение х ~/ у эквивалентно выражению -х -+ у. Приведите задачу 2-СХР Блт к задаче на ориентированном графе, имеющей эффективное решение.) 34.5 ХР-полные задачи ХР-полные задачи возникают в различных областях: в булевой логике, в теории графов, в арифметике, при разработке сетей, в теории множеств и разбиений, при хранении и поиске информации, при планировании вычислительных процессов, в математическом программировании, в алгебре и теории чисел, при создании игр и головоломок, в теории автоматов и языков, при оптимизации программ, в биологии, в химии, физике и т.п.
В настоящем разделе с помощью методики приведения будет доказана ХР-полнота различных задач, возникающих в теории графов и при разбиении множеств. На рис. 34.12 приводится схема доказательства ХР-полноты, которая используется в этом разделе и в разделе 34.4. Для каждого из представленных на рисунке языков ХР-полнота доказывается путем приведения его к языку, на который Часть Ч1!. Избранные темы 1128 г сйсбп'-5Ат~з Сз-Снг-зАт "1 уБгтвх-сочдя ( НАЯ4"~Ш.
.-(- ~ ТБР ) Рнс. 34.12. Схема доказательств 1чР-полноты для задач, рассматриваемых в разделах 34.4 и 34.5; все доказательства в конечном итоге сводятся к приведению 1чР-полной задачи Свплт ЯАт к рассматриваемой указывает идущая от этого языка стрелка. В качестве корневого выступает язык Сасщт ЯАт, ХР-полнота которого доказывается в теореме 34.7.
34.5.1 Задача о клике Ялика (с!и)пе) неориентированного графа С = Я Е) — это подмножество У' С У вершин, каждая пара в котором связана ребром из множества Е. Другими словами, клика — это полный подграф графа С. Размер (з(хе) клики — это количество содержащихся в нем вершин. Задача о клике (с11с)пе ргоЫеш) — это задача оптимизации, в которой требуется найти клику максимального размера, содержащуюся в заданном графе. В соответствующей задаче принятия решения спрашивается, содержится ли в графе клика заданного размера lс. Формальное определение клики имеет вид С~Оин = ((С, к): С вЂ” граф с кликой размера Ц . Простейший алгоритм определения того, содержит ли граф С = (К Е) с ~Ц вершинами клику размера й, заключается в том, чтобы перечислить все )с-элементные подмножества множества У, и проверить, образует ли каждое из них клику.
Время работы этого алгоритма равно й (йз (~, ~) ) и является полиномиальным, если )с — константа. Однако в общем случае величина к может достигать значения, близкого к Щ/2, и в этом случае время работы алгоритма превышает Глава 34. ХР-полнота 1129 полиномиальное. Есть основания предполагать, что эффективного алгоритма для задачи о клике не существует. Теорема 34.11.
Задача о клике является ХР-полной. Доказаюельсиыо. Чтобы показать, что СыопвеХР для заданного графа С = = (1/, Е), воспользуемся множеством 1/' С 1/ вершин клики в качестве сертификата для данного графа. Проверить, является ли множество вершин 1/' кликой, можно в течение полиномиального времени, проверяя для каждой пары вершин и, о Е 1/', принадлежит ли соединяющее их ребро 1и, о) множеству Е. Теперь докажем, что 3-СХР Блт <р С1201/н, откуда следует, что задача о клике является ХР-сложной. То, что этот результат удается доказать, может показаться удивительным, потому что на первый взгляд логические формулы мало напоминают графы. Построение алгоритма приведения начинается с экземпляра задачи 3-СХР ЯАт.
Пусть ф = С2 Л С2 Л Л Сь — булева формула из класса 3-СХР с й подвыражениями в скобках. Каждое подвыражение С, при г = 1, 2,..., й содержит ровно три различных литерала 1» 12, и 12. Сконструируем такой граф С, чтобы формула ф была выполнима тогда и только тогда, когда граф С содержит клику размера 1с. Это делается так. Для каждого подвыражения С, = Я ~/ 12 Ч 12) в формуле ф в множество 1/ добавляется тройка вершин о~, и2 и изг. Вершины иг н о' соединяются ребром, если справедливы оба сформулированных ниже утверждения: ° вершины ог и о' принадлежат разным тройкам, т.е. г ф з; ° литералы, соответствующие этим вершинам, совместимы (сопз1з1еп1), т.е. 1; не является логическим отрицанием 1'.
Такой граф легко построить на основе формулы ф в течение полиномиального времени. В качестве примера на рис. 34.13 приведен граф С, соответствующий формуле ф = (Х1 ~/ 'Х2 ~/ 'ХЗ) Л ( 'Х1 ~/Х2 ~/ХЗ) Л (Х1 ~/Х2 ~/ХЗ). Необходимо показать, что это преобразование формулы ф в граф С является приведением. Во-первых, предположим, что для формулы ф имеется выполняющий набор. Тогда каждое выражение С„ содержит не менее одного литерала 1,", значение которого равно 1, и каждый такой литерал соответствует вершине о,'. В результате извлечения такого "истинного'* литерала из каждого подвыражения получается множество 1/', состоящее из й вершин. Мы утверждаем, что 1/' — клика.
Для любых двух вершин о,", о' е 1/', где т ф з, оба соответствующих литерала 1; и 1' при данном выполняющем наборе равны 1, поэтому онн не могут быть отрицаниями друг друга. Таким образом, в соответствии со способом построения графа С, ребро (о,", ю') принадлежит множеству Е. Часть Ч!1. Избранные темы 1130 Рис. 34.13. Граф С, полученный в процессе приведения задачи 3-СИР БАт к задаче Сыапв Проведем обратные рассуждения.
Предположим, что граф С содержит клику У' размера й. Ни одно из ее ребер не соединяет вершины одной и той же тройки, поэтому клика У' содержит ровно по одной вершине каждой тройки. Каждому литералу 1;, такому что цт Е У', можно присвоить значение 1, не опасаясь того, что это значение будет присвоено как литералу, так н его дополнению, поскольку граф С не содержит ребер, соединяющих противоречивые литералы. Каждое подвыражение в скобках является выполнимым, поэтому формула ф тоже выполнима. (Переменным, которым не соответствует ни одна вершина клики, можно присваивать произвольные значения.) И В примере, представленном на рис. 34.13, выполняющий набор для формулы 4 имеет вид хз = О и кз = 1.
Соответствующая клика размера й = 3 состоит из вершин, отвечающих литералу хз из первого подвыражения в скобках, литералу кз из второго выражения в скобках и литералу хз из третьего выражения в скобках. Поскольку клика не содержит вершин, соответствующих литералу х~ или литералу тп переменная хг в выполняющем наборе может принимать как значение О, так и значение 1. Обратите внимание, что при доказательстве теоремы 34.11 произвольный экземпляр задачи 3-СИР БАт был сведен к экземпляру задачи СыООн, обладающему определенной структурой. Может показаться, что принадлежность задачи Сьи3ОЕ категории ХР-сложных была доказана лишь для графов, все вершины которых можно разбить на тройки, причем таких, в которых отсутствуют ребра, соединяющие вершины одной и той же тройки.
В самом деле, ХР-сложность задачи СыОы была показана только для этого ограниченного случая, однако этого до- Глава 34. ХР-полнота 1131 казательства достаточно, чтобы сделать вывод о ХР-сложности этой задачи для графа общего вида. Почему? Дело в том, что из наличия алгоритма с полиномиальным временем работы, решающего задачу Сщг?пв с графами общего вида, следует существование такого алгоритма решения этой задачи с графами, имеющими ограниченную структуру. Однако было бы недостаточно привести экземпляры задачи 3-СХР Блт, обладающие какой-то особой структурой, к экземплярам задачи Сыцил общего вида. Почему? Может случиться так, что экземпляры задачи 3-СХР Блт, с помощью которых выполняется приведение, окажутся слишком "легкими", и к задаче Сыапл приводится задача, не являющаяся ХР-сложной.
Заметим также, что для приведения используется экземпляр задачи 3-СХР Блт, но не ее решение. Было бы ошибкой основывать приведение в течение полиномиального времени на знании того, выполнима ли формула ф, поскольку неизвестно, как получить эту информацию в течение полиномиального времени. 34.5.2 Задача о вершинном покрытии Вершинное покрытие (чеггех сечет) неориентированного графа С = (К Е)— это такое подмножество У' С 'ч', что если (н,ч) е Е, то и е У' либо ч Е 1н (либо справедливы оба эти соотношения).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
