Алгоритмы - построение и анализ (1021735), страница 233
Текст из файла (страница 233)
Каждая строка такой таблицы соответствует одному из вариантов набора, и содержит сам вариант и результат вычисления исследуемого выражения. С помощью элементов таблицы истинности, которые приводят к нулевому результату в формуле, можно составить формулу, эквивалентную выражению — ф';, в дизъюнктиеной нормальной форме (!31з)ппсцче Хоппе! Ропп, 0ХР), которая является дизъюнкцией конъюнкций. Затем эта формула с помощью законов де Моргана (1)еМогяав) Глава 34. ХР-полнота 1125 (уравнение (Б.2)) преобразуется в СХР-формулу 4>1 путем замены всех литералов их дополнениями и замены операций дизъюнкций и конъюнкций друг на друга. В качестве примера преобразуем выражение 4~ —— (уз + (уз Л ~хз)) в СХР.
Таблица истинности для этой формулы представлена в табл. 34.1. ПХР-формула, эквивалентная выражению — ф', имеет вид (уз л уз л хз) ч (уз л уз л хз) ч (у~ л уз л . хз) ч (- уз л уз л . хз). Применяя законы де Моргана„получим СХР-формулу ф~ = ( 'У1 Ч Уз Ч - хз) Л (-'уз Ч Уз Ч вЂ” хг) Л ( 'уз Ч Уз Ч хз) Л (у~ Ч вЂ” Уз Ч хз), которая эквивалентна исходной формуле ф',. Таблица 34.1.
Таблица истинности для выражения (у~ ~ (уя Л хз)) После того как каждое подвыражение ф',, содержащееся в формуле ф', оказывается преобразовано в СХР-формулу ф,", так что ф эквивалентно СХР-формуле ф", состоящей из конъюнкции выражений ф'. Кроме того, каждое подвыражение формулы фл содержит не более трех литералов. На третьем и последнем этапе приведения формула преобразуется таким образом, чтобы в каждых скобках содержалось точно 3 различных литерала. Полученная в результате 3-СХР формула ф'л составлена из подвыражений, входящих в СХР-формулу ф". В ней также используются две вспомогательные переменные, которые будут обозначаться как р и д.
Для каждого подвыражения С; из формулы 4)" в формулу ф"' включаются следующие подвыражения. ° Если С; содержит 3 различных литерала, то это подвыражение включается в формулу ф"' в неизменном виде. ° Если выражение С; содержит 2 различных литерала, т.е. если С; = (1~ Ч 1з), где 1з и 1з — литералы, то в качестве подвыражения в формулу ф"' включается выражение (1~ Ч 1з Ч р) Л (1~ Ч 1я Ч. р). Литералы р и -р служат лишь Часть ЧП. Избранные темы 1126 для того, чтобы удовлетворялось требование о наличии в каждом подвыражении в скобках ровно трех разных литералов: выражение (11 Ч 1з Ч р) Л (11 Ч 1з Ч р) эквивалентно выражению (11 Ч 1з) и при р = О, и при р = 1. ° Если выражение С; содержит ровно 1 литерал 1, то вместо него в качестве подвыражения в формулу ф"' включается выражение (1 Ч р Ч д) Л (1ЧрЧ-9) Л (1 Ч рЧд) Л (1Ч- рЧ- д).
При любых значениях переменных р и д приведенная конъюнкция четырех подвыражений в скобках эквивалентна 1. Проверив каждый из описанных выше трех этапов, можно убедиться, что 3-СХР формула ф"' выполнима тогда и только тогда, когда выполнима формула ф. Как и в случае приведения задачи Сшсшт Блт к задаче Ялт, составление на первом этапе формулы ф' по формуле я) не повлияет на выполнимость.
На втором этапе конструируется СХР-формула ф", алгебраически эквивалентная формуле ф'. На третьем этапе конструируется 3-СХГ формула ф"'; результат которой эквивалентен формуле ф", поскольку присваивание любых значений переменным р и д приводит к формуле, алгебраически эквивалентной формуле ф".
Необходимо также показать, что приведение можно выполнить в течение полиномиального времени. В ходе конструирования формулы ф'по формуле ф приходится добавлять не более одной переменной и одной пары скобок на каждый соединительный элемент формулы ф. В процессе построения формулы фл по формуле 4' в формулу фл добавится не более восьми подвыражений в скобках на каждое подвыражение в скобках из формулы 4', поскольку каждое подвыражение в этой формуле содержит не более трех переменных и таблица его истинности состоит не более чем из 2з = 8 строк. В ходе конструирования формулы ф"' по формуле ф" в формулу фл' добавляется не более четырех подвыражений на каждое подвыражение формулы ф".
Таким образом, размер полученной в результате формулы фл' выражается полиномиальной функцией от длины исходной формулы. Следовательно, каждый этап можно легко выполнить в течение полиномиального времени. й Упражнения 34.4-1. Рассмотрите приведение "в лоб" (время работы которого не выражается полиномиальной функцией) из теоремы 34.9. Опишите схему размера а, размер которой после преобразования этим методом превратится в формулу размер которой выражается показательной функцией от и. 34.4-2.
Приведите 3-СХР формулу, которая получится в результате применения метода, описанного в теореме 34.10, к формуле (34.3). 34.4-3. Профессор предложил показать, что Злт <г 3-СХГ Блт, лишь с помощью метода с использованием таблицы истинности, описанного в до- Глава 34. ХР-полнота 1127 казательстве теоремы 34.10, исключая при этом другие этапы. Другими словами, профессор предложил взять булеву формулу ф, составить таблицу истинности для ее переменных, получить из нее формулу в 3-13ХР, эквивалентную ~ф, после чего составить логическое отрицание полученной формулы и с помощью законов де Моргана получить 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-СХР Блт <р Си01/н, откуда следует, что задача о клике является ХР-сложной. То, что этот результат удается доказать, может показаться удивительным, потому что на первый взгляд логические формулы мало напоминают графы.
Построение алгоритма приведения начинается с экземпляра задачи 3-СХР ЯАт. Пусть ф = С2 Л С2 Л Л Сь — булева формула из класса 3-СХР с й подвыражениями в скобках. Каждое подвыражение С, при г = 1, 2,..., й содержит ровно три различных литерала 1» 12, и 12. Сконструируем такой граф С, чтобы формула ф была выполнима тогда и только тогда, когда граф С содержит клику размера 1с. Это делается так. Для каждого подвыражения С, = Я ~/ 12 Ч 12) в формуле ф в множество 1/ добавляется тройка вершин о~, и2 и изг. Вершины иг н о' соединяются ребром, если справедливы оба сформулированных ниже утверждения: ° вершины ог и о' принадлежат разным тройкам, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
