(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) (1186152), страница 13
Текст из файла (страница 13)
Для каждой четверки(*» /, к, I),0< / < р ( д ) , - / ф ) < / < р ( « ) + ],эта подгруппа содержит следующие три дизъюнкции:(ЖТ1 ЩГТьЖТП. Я1Н-1, /+А]},№/I- i i mЩ1, QU +1Ш Uh йИь М> ЩГГТЬ,к i'})>где значения А, к' и /' определены так:«СЛЙ q:k S Q \ { % ,а еслито 6 ( % s{) =(< £ , VА ),gN}, то А — 0, к* = к и Г = LНетрудно понять, что эти 6p(n)(p(n)+l)(r+l)(v+l)дизъюнкций дают необходимое ограничение на выполняющийнабор значении истинности.Таким образом, мы показали, как построить группыдизъюнкций Gi~G6 которые выполняют свое назначение.Если хе L, то у программы М на входе х есть принимающеевычисление длины не более р(п), и это вычисление дает призаданной интерпретации переменных набор значенийистинности, который выполнит все дизъюнкции из C=Gi u G2и G3и G4 и Gs и G6. И наоборот, набор дизъюнкций Спостроен так, что любой выполняющий набор значенийистинности для С обязан соответствовать некоторомупринимающему вычислению программы М на входе х.Отсюда следует, что для fi(x) имеется выполняющий наборзначений истинности тогда и только тогда, когда хе L.Теперьосталосьпоказать,чтодлялюбогофиксированного языка L индивидуальная задача f L(x) можетбыть построена за время, ограниченное полиномом от п=\х|.Если язык L задан, то можно выбрать некоторую НДМТпрограмму М, которая распознает L за время, ограниченноеполиномом р (нет необходимости за полиномиальное времянаходить саму недетерминированную программу, так какнеобходимо лишь показать, что отображение f L существует).Если имеются определенная НДМТ-программа М и многочленр, то построение множества переменных U и наборадизъюнкций С требует чуть больше работы, чем заполнениевсех позиций в стандартной (хотя и довольно сложной)формуле.
Полиномиальная ограниченность этого вычислениябудет ясна, если мы покажем, что Length \fiix)] ограниченасверху полиномом от п, где Length [I] характеризует длинуслова, кодирующего индивидуальную задачу I при некоторойразумной схеме кодирования.В качестве «разумной» функции длины для задачи ВЫПможно, например, взять JТУ|-(С'|. Ни одна из дизъюнкций неможет содержать более 2-\U\ литералов (т. к. общее числолитералов равно 2-|U|), а число символов, необходимое дляописания каждого индивидуального литерала, не более log\U\,но этой величиной можно пренебречь, так как она даетполиномиальный вклад в общую длину задачи.
Поскольку г иv фиксированы заранее, то они могут увеличить |С/| и |С| впостоянное число раз, поэтому имеем, что мощности\U\=0(p2(n))и\С\=0(р2{п)).Следовательно,Length\fL(x)]=\U\-\C\=0(p4(ri))и,значит,ограниченаполиномом от п, что и требовалось доказать.Таким образом, преобразование f L может быть вычисленоалгоритмом,имеющимполиномиальнуювременнуюсложность (однако конкретная полиномиальная граница длясложности будет зависеть от L, а также от выбора М и р), изчего можно заключить, что для всех Le NP функция f Lвычислима за полиномиальное время и отображает L в ВЫП(точнее, отображает L в 1пы„). Отсюда вытекает утверждениетеоремы, что ВЫП - NP-полная задача.ГЛАВА 5.
КЛАСС NP-ПОЛНЫХ ЗАДАЧЕсли бы все доказательства NP-полноты были так жесложны,какдоказательствоNP-полнотызадачиВЫПОЛНИМОСТЬ, то очень сомнительно, что список NPполных задач смог бы стать столь обширным, как в настоящеевремя. Однако, как указывалось выше, если уже известна однаNP-полная задача, то процедура доказательства NP-полнотыдругих задач значительно упрощается. Для доказательства NPполноты задачи П eNP достаточно показать, что какая-нибудьиз известных NP-полных задач П' может быть сведена к П.Таким образом, в дальнейшем процесс доказательства NPполноты задачи распознавания П будет состоять изследующих четырех шагов:(1) доказательства того, что П лежит в NP;(2) выбора известной NP-полной задачи П';(3) построения функции f сводящей задачу П' к задаче П, и(4) доказательства того, что функция / осуществляет полиномиальное сведение.Цель настоящей главы состоит не только в том, чтобыознакомить читателей с конечными результатами этогопроцесса (с окончательными доказательствами NP-полноты),но также и в том, чтобы подготовить их к самостоятельномупоиску таких доказательств.Ниже приводятся 6 задач, которыми чаше других пользуются при доказательстве результатов об NP-полноте в качестве известных NP-полных задач и доказывается NP-полнотаэтих шести задач.
Затем приводится описание трех общихподходов к установлению сводимости задач и дается их иллюстрация посредством доказательства NP-полноты большогочисла различных задач. В заключение приводится несколькорезультатов об NP-полноте, которые предлагается доказатьчитателю.ШЕСТЬ ОСНОВНЫХ NP-ПОЛНЫХ ЗАДАЧКогда практику встречается задача П, NP-полнотукоторой требуется доказать, его преимущество заключается втом, что он имеет богатый выбор путей такого доказательства.Вполне может случиться, что в прошлом он уже доказывалили видел доказательство NP-полноты похожей задачи ГГ.
Эгоможет привести к мысли попытаться построить доказательство NP-полноты задачи П, копируя доказательствоNP-полноты задачи П', или просто сводя задачу ГГ к задаче П.Во многих случаях это может привести к достаточно простомудоказательству NP-полноты задачи П.Но очень часто не удается найти NP-полную задачу,похожую на П. В таких случаях практику может быть не ясно,какая из сотен известных NP-полных задач лучше всегоподходит в качестве основы искомого доказательства. Однакопредыдущий опыт может оказаться полезным дляограничения области выбора некоторым ядром из базовыхзадач, использовавшихся ранее. Хотя теоретически любую изизвестных NP-полных задач можно наравне с другимивыбрать для доказательства NP-полноты новой задачи, напрактике оказывается, что некоторые задачи подходят дляэтой цели гораздо лучше других.
Следующие шесть задачвходят в число тех, которые используются наиболее часто имогут служить основным ядром списка известных NP-полныхзадач.3-ВЫПОЛНИМОСТЬ (3-ВЫП)УСЛОВИЕ. Дан набор С={с/, с2, ... , ст} дизъюнкций на конечном множестве переменных U, таких, что |с,| = 3, 1 < / <т.ВОПРОС.
Существует ли на U набор значений истинности,при котором выполняются все дизъюнкции из С?ТРЕХМЕРНОЕ СОЧЕТАНИЕ (3-С)УСЛОВИЕ. Дано множество /И£ №X * X У, где W, X и Y —непересекающиеся множества, содержащие одинаковое числоэлементов q.ВОПРОС. Верно ли, что М содержит трехмерное сочетание, т.е. подмножество M t М, такое, что \M'\=q и никакие дваразных элемента М' не имеют ни одной равной координаты?ВЕРШИННОЕ ПОКРЫТИЕ (ВП)УСЛОВИЕ. Дан граф G=(V,E) и положительное целое число Ктакое, что K<\V\.ВОПРОС.
Имеется ли в графе G вершинное покрытие неболее чем из К элементов, т. е. такое подмножество F t V., что\V'\<K и для каждого ребра {и, v}<= Е хотя бы одна из вершин иили v принадлежит VIТ.е можно ли найти подмножество вершин (не более К ) такое,что для каждого ребра из исходного графа хотя бы одна издвух вершин была бы в выбранном подмножеств?КЛИКАУСЛОВИЕ.
Дан граф G=(V,E) и положительное целое числоМЛВОПРОС. Верно ли, что G содержит некоторую клику мощности не менее J, т. е. такое подмножество F t V, что \V’\>J илюбые две вершины из V соединены ребром из Е?Т.е. содержит ли граф связный подграф, включающий > Jвершин?ГАМИЛЬТОНОВ ЦИКЛ (ГЦ)УСЛОВИЕ. Дан граф G= (V.E).ВОПРОС.
Верно ли, что G содержит гамильтонов цикл, т. е.такую последовательность <V],v2, ... ,v„> вершин графа G, чтоп=|F|, {v„,v/}e Е и {Vi,v,.j}eE для всех /, l<i<n.Т.е. существует ли цикл, проходящий через все вершиныграфа ровно по одному разу и возвращающийся в начальнуюточку?РАЗБИЕНИЕУСЛОВИЕ. Заданы конечное множество А и «вес» s(a)e Zдля каждого ае А.ВОПРОС. Существует ли подмножество Л 'с Л, такое, чтоs(a)=*V&(а )?а еЖен&А'ЫьА'Можно ли разбить множество А на два подмножества так,чтобы их суммарные «веса» были равны?ВЫПОЛНИМОСТЬ3-ВЫП3 -С\РАЗВивниев п/гиN,кликаР ис .5.1.Диаграммапоследовательности сведенияз адач, используемыхиспользуемых для доказательства NP-полноты шести основных задачОдна из причин популярности этих шести задачзаключается в том, что все они содержались в исходномсписке из 21 NP-полной задачи, приведенном в одной из работКарпа.Начнем демонстрацию методов доказательства NPполноты с доказательства NP-полноты этих шести задач,указывая в подходящих случаях такие их варианты, NPполнота которых более или менее непосредственно следует изNP-полноты этих шести задач.Первая сводимость будет получена с помощью задачиВЫПОЛНИМОСТЬ, поскольку пока это единственная задачаNP-полноту, которой мы установили.
Однако по мере доказательства NP-полноты этих шести задач список NP-полныхзадач будет расширяться и доказательство NP-полнотынекоторой задачи может быть получено с использованиемлюбой из задач, NP-полнота которой установлена раньше, чемдля задачи П. На рис. 5.1 указана последовательностьсведения задач, которая применяется в доказательстве NPполноты шести основных задач, причем если стрелка ведет отодной задачи к другой, то первая сводится ко второй.3-ВЫПОЛНИМОСТЬЗадача 3-ВЫПОЛНИМОСТЬ есть просто ограниченный вариант задачи ВЫПОЛНИМОСТЬ, в котором каждаяиндивидуальная задача имеет ровно три литерала в каждойдизъюнкции. Из-за своей простой структуры эта задачанаиболее часто применяется для доказательства результатовоб NP-полноте.Теорема 5.1. Задача 3-ВЫПОЛНИМОСТЬ является NPполной.Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
