Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 253
Текст из файла (страница 253)
На третьем (и последнем) этапе приведения формула преобразуется таким образом, чтобы в каждой паре скобок содержалось ровно три различных литерала. Полученная в результате окончательная 3-СХГ формула ф"' составлена из подвыражений, входящих в СХГ-формулу фл. В ней также используются две вспомогательные переменные, которые будут обозначаться как р и о. Для каждого подвыражения С; из формулы (ал в формулу фл' включаются следующие подвыражения. Если С, содержит три различных литерала, то это подвыражение включается в формулу ф'н в неизменном виде. Если подвыражение С, содержит два различных литерала, т.е. если С; = (11 ч 12), где 11 н 12 — литералы, то в качестве подвыражения в формулу фм включается выражение 11 '~ 12'Ч р) А (11 Ч 12 '~ - р). Литералы р и - р служат лишь для того, чтобы удовлетворялось требование о наличии в каждом подвыражении в скобках ровно трех разных литералов: когда р = О или р = 1, одно из подвыражений эквивалентно 11 'у' 12, а второе — единице, что н обеспечивает тождественность первому из упомянутых подвыражений при применении операции И.
Если подвыражение С, содержит ровно одни литерал 1, то вместо него в качестве подвыражения в формулу ф"' включается подвыражение (1 Ч р Ч д) А (1 Ч р Ч вЂ” д) А (Н - р Ч о) А (1 Ч р Ч вЂ” о). При любых значениях переменных р н о одно из четырех подвыражений равно 1, а прочие три равны единице. Проверив каждый из описанных выше трех этапов, можно убедиться, что 3-СХг формула ф" выполнима тогда и только тогда, когда выполнима формула ф.
Как и в случае приведения задачи С1НС(ПТ-БАТ к задаче ЯАТ, составление на первом этапе формулы ф из формулы ф не влияет на выполнимость. На втором этапе конструируется СХГ-формула фл, алгебраически эквивалентная формуле ф'. На третьем этапе конструируется 3-СХЕ формула ф"', результат которой эквивалентен формуле ф", поскольку присваиванне любых значений переменным р и д приводит к формуле, алгебранчески эквивалентной формуле с)". Глава ЗК ФР-иавиаеа ПЗ5 Необходимо также показать, что приведение можно выполнить за полиномиальное время. В ходе юнструирования формулы ф' по формуле ф приходится добавлять не более одной переменной и одного подвыражения на каждый соединительный элемент формулы ф. В процессе построения формулы фа из формулы ф' в формулу фи добавляется не более восьми подвыражений для каждого подвыражения в скобках из формулы ф', посюльку каждое подвыражение в этой формуле содержит не более трех переменных и таблица его истинности состоит не более чем из 2з = 8 строк.
В ходе юнструирования формулы фи' из формулы ф" в формулу фи' добавляется не более четырех подвыражений на каждое подвыражение формулы ф". Таким образом, размер полученной в результате формулы фи' выражается полнномиальной функцией от длины исходной формулы. Следовательно, каждый этап можно легко выполнить за полиномиальное время. ° Упражнения 34.4.1 Рассмотрите простое приведение "в лоб" (время работы которого не выражается полиномиальной функцией) из теоремы 34.9.
Опишите схему размера и, размер которой после преобразования этим методом превратится в формулу, размер которой выражается показательной функцией от п. 34.4.2 Приведите 3-СХР формулу, которая получится в результате применения метода, описанного в теореме 34.10, к формуле (34.3). 34.4.3 Профессор предложил показать, что ЯАТ <р З-Сг(Р-БАТ, лишь с помощью метода с использованием таблицы истинности, описанного в доказательстве теоремы 34.10, исключая при этом другие этапы.
Другими словами, профессор предложил взять булеву формулу ф, составить таблицу истинности для ее переменных, получить из нее формулу в З-ПИР, эквивалентную — ф, после чего составить логическое отрицание полученной формулы и с помощью законов де Моргана получить формулу 3-САЯР, эквивалентную формуле ф. Покажите, что в результате применения такой стратегии не удается выполнить приведение формулы за полиномиальное время. 34.4.4 Покажите, что задача определения того, является ли тавтологией данная формула, является полной в классе со-г(Р.
(Указание: см. упр. 34.3.7). 34.4.3 Покажите, что задача определения выполнимости булевых формул в дизъюнктивной нормальной форме разрешима в течение полиномиального времени. 34.4.6 Предположим, что ато-то разработал алгоритм с полиномиальным временем выполнения, позволяющий решить задачу о выполнимости формул.
Опишите, как И36 Часть Ги Избраьтые теяьь с помощью этого алгоритма в течение полиномиального времени находить вы- полняющие наборы. 34.4. 7 Пусть 2-СХГ-ЯАТ вЂ” множество выполнимых булевых формул в СХР, у которых каждое выражение в скобках содержит ровно по два литерала. Покажите, что 2-СХЕ-БАТ Е Р.
Постарайтесь, чтобы ваш алгоритм был как можно более эффективным. (Указаниес воспользуйтесь тем, что выражение х Ч у эквивалентно выражению х -+ у. Приведите задачу 2-СХР-ЯАТ к задаче на ориентированном графе, имеющей эффективное решение.) 34.5. ХР-нолпые задачи ХР-полные задачи возникают в различных областях: в булевой логике, в теории графов, в арифметике, при разработке сетей, в теории множеств и разбиений, при хранении и поиске информации, при планировании вычислительных процессов, в математическом программировании, в алгебре и теории чисел, при создании игр и головоломок, в теории автоматов и языков, при оптимизации программ, в биологии, в химии, физике и т,п.
В настоящем разделе с помощью методики приведения будет доказана ХР-полнота различных задач, возникающих в теории графов и при разбиении множеств. На рис. 34.13 приведена схема доказательства ХР-полноты, которая используется в этом разделе и в разделе 34.4. Для каждого из представленных на рисунке языков ХР-полнота доказывается путем его приведения к языку, на который указывает идущая от этого языка стрелка. В качестве корневого выступает язык С1В.СШТ-БАТ, ХР-полнота которого доказана в теореме 347Е 34.5.1.
Задача о клике Клика (с11с)це) неориентированного графа С = (Ъ; Е) — зто подмножество Г ь У вершин, каждая пара в котором связана ребром из множества Е. Другими словами, клика — зто полный подграф графа С. Размер (з)ге) клики — это количество содержащихся в этом подграфе вершин. Задача о «лике (с1к)це ргоо)еш)— это задача оптимизации, а которой требуется найти клику максимального размера, содержащуюся в заданном графе. В соответствующей задаче принятия решения спрашивается, содержится ли в графе клика заданного размера к. Формальное определение языка имеет вид СЫЯ1)Е = ((С, 1с): С вЂ” граф„содержащий клику размером )с) Простейший алгоритм определения того, содержит ли граф С = (У, Е) с 1У~ вершинами клику размером )с, заключается в том, чтобы перечислить все й-элементные подмножества множества У и проверить, образует ли каждое из иих клику.
Время работы этого алгоритма равно П(кг(1ь1) ) и является полиномиаль- Глава 34. ИР-котлета Рис. 34ДЗ. Схема доказательств МР-полноты задач, рассматриваемых в разделах 34.4 и 34.5. Все доказательства в конечном итоге сводьтсл к приведению 1ЧР-полиой задачи СЖСЛТ-ЯАТ к рассматриваемой. ным, если /с — константа. Однако в общем случае величина А может достигать значения, близкого к ~Ц /2, н в этом случае время работы алгоритма превышает полнномиапьное. Есть основания предполагать, что эффективного алгоритма для задачи о клике не существует. Теорема з4.41 Задача о клике является 1чР-полной.
Доказаагельсглегх Чтобы показать, что СЕ1ЯБЕ е ХР, для заданного графа С = (1', Е), воспользуемся множеством Рч С ьг вершин клики в качестве сертификата для данного графа. Проверить, является ли множество вершин Ъ" кликой, можно в течение полиномиального времени, проверяя для каждой пары вершин и, и е 1", принадлежит ли соединяющее их ребро (и, и) множеству Е. Теперь докажем, что 3-С1чр-ЯАТ <р С1ЛЯ11Е, откуда следует, что задача о клике является МР-сложной.
То, что этот результат удается доказать, может показаться удивительным, потому что, на первый взгляд, логические формулы мапо напоминают графы. Алгоритм приведения начинается с экземпляра задачи 3-СХР-ЯАТ. Пусть ф = Ст ЛСзЛ .ЛСь — булева формула из класса ЗС1чр с ~с подвыражениями. Каждое подвыражение С„при г = 1, 2,..., А содержит ровно три различных литерала— 1', 1з и 13.
Сконструируем такой граф С, чтобы формула ф была выполнима тогда и только тогда, когда граф С содержит клику размера lс. Граф С = (Ъ; Е) мы строим следующим образом. Для каждого подвыражения С, = (11 'ч' 1з и 13) в ф помещаем тройку вершин, йм из и из, в ь". Вершины иг и оч соединяются ребром, если справедливы оба следующих утверждения: и," и и' находятся в разных тройках, т.е. г зь л; и их литералы соамесагимы, т.е. 1; не является отрицанием 1'.
Часть И1. Избранные златы изб С1 =хгы-хгц хз Сз = хг мха цхз Сз = хз Чхзцхз Рае. 34.14. Граф С, полученный в процессе приведения 3-С)чр-БАТ к задаче С1ЛЯ))Е из 3-С1ЧР- формулы ф = С1 дСз лСз, где С| = (х, 'з хз 'з хз), Сз = ( х, ухач хз) и Сз = (хз ц хз и хз) Выполняющий набор формулы включает хз = О, хз = 1, а х, может быль как нулем, так и единицей. Зтст набор выполняет С1 благодаря хг, н Сг н Сз благодаря хз, соотаегствуя клике из выделениык светлой штриховкой вершин. Такой граф легко построить для формулы ф за полиномиальное время.
В качестве примера на рис. 34.14 приведен граф С, соответствующий формуле ф = (Хг ГУ ХЗ Ч ХЗ) Д ( зХ1 Ч ХЗ ГУ ХЗ) Л (Хг ГУХЗ Ч ХЗ) Необходимо показатзч что это преобразование формулы ф в граф С является приведением. Во-первых, предположим, что для формулы ф имеется выполняющий набор. Тогда каждое подвыражение С, содержит не менее одного литерала 1;, значение которого равно единице, и каждый такой литерал соответствует вершине н,'. В результате извлечения такого "истинного" литерала нз каждого подвыражения получается множество )г', состоящее из )с вершин. Мы утверждаем, что и" — клика. Для любых двух вершин и,', и' е ьгг, где т ф з, оба соответствующих литерала, 1," и 1', при данном выполняющем наборе равны единице, поэтому они не могут быть отрицаниями один другого.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
