Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 72
Текст из файла (страница 72)
Булева формула Р(х) будет содержать следующие булевы пере менные. 1. Булевы переменные хы, для всех 0<1, 1<р()х!) и о Е Х. Переменная хы, будет соответствовать утвеждению: !ця позиция строки в момент времени 1 содержигп символ о. 2. Булевы переменные у,н для всех 0а=М,р()х!), 0 =7<р()х!)+ +1 и 1<!<1А), где )и71 — число команд в алгоритме Х Перемен.
ная уы, будет соответствовать утверждению: в момент времени ! обозревпется )ця позиция и выполняется 1-я команда. Если 1=0 или 1=р(1х!)+1, то это означает, что головка сошла со строки и, следовательно, вычисление безуспешно. Построим ~еперь из этих булевых переменных такую формулу Р(х), что Р(х) выполнима тогда и только тогда, когда х — это индивидуальная задача задачи А с ответом да. Если булевы переменные имеют указанный смысл, то Г(х), будет, по существу, утверждать, что алгоритм А, начиная работу со строкой, в левой части которой стоит х, може~ в результаге принять эту строку; по опреде- /в.в. теорема кука 367 ленив это будет означать, что существует подходящее удостоверение с(х) и, следовательно, что х — индивидуальная задача задачи А с ответом да. Формула г"(х) является конъюнкцией четырех частей: г"(х)=(/(х) 5(х) уй'(х) Е(х). 1.
Подформула (/(х) выражает тот факт, что в каждый момент времени ), 0<1<р(1х!) в каждой позиции строки содержится единственный символ, головка обозревает единственную позицию в пределах строки и программа выполняет единсл)еенный оператор. (/ (х) =)/ Ц (хио+ х)).о ) )Хоч',);опон о=о' П (у)/)+У~с)й)' П У)о)'У), опор+),с ок о))оп Ом)о,р~) » П )~!' ооо ) ~)' Л ) ч )<!о(1 Оч) ч о)! ~ О~ ~) ч), о)! о !) о ох / ) ч)ЧРП ~!) /)/) ) ч)ч1о(1 2.
Формула 5(х) утверждает, что о! корректно начинает работу: другими словами, в нулевой момент времени самые левые !х)+! символов в строке образую) слово х~, читающая-пишущая головка обозревает самый левый символ строки и программа переходит к выполнению первой команды алгоритма: /)о! 5 (х) =~ П хо/ю/) 'Хо, )о )о), я'уоы (Здесь х(!) обозначает 1-й символ строки х.) 3; Формула (Р'(х) утверждает, что о7 работает правильно в соотве)стяни с командами программы; у(/(х) является конъюнкцией формул )рц„, по одной для каждых 0о='1<р((х!), !<1<р()х~), пЕ Х, 1<!<!о7(, таких, что 1-я команда алгоритма о! имеет вид 1; 1! а!))еп(а', о; !').
Формула В'цо) определяется следующим образом) ))7))о) = (хио + у)/)+х)н, ), о ) ' (хио+ у)/)+ у))!, ььо, и) П ((х)п+ у)/)+ х)+), ), о)'(хн1+ у;/)+ У|+). ). )+~)). Она означает, что если хц, и уц, оба истинны, то в следующий момент времени переменные х и у, утверждающие, что алгоритм А выполнил правильные действия, также должны быть истинными. Для последней команды алгоритма о1 и для каждых ), !и а добавляется формула )(/по!А!= (хио+ У)) 1 'Е !+ У)+ц ъ1А 1) утверждающая, что как только алтари)м достигает команды ассерг, он остается в этом положении. Кроме гого, В'(х) содержит дизъюн- Гж !6. ХР-оокние эодочи 368 кты П (Х))о+ У)1'1+Х)+1, 1, о), О <1< р1)к)) оев 1~1~(А! )М ) означающие, что если А обозревает позицию, отличную от )ъй, то символ в Г-й позиции остается неизменным, 4.
Последняя часть формулы Е(х) утверждает просто, что Г корректно заканчивает свою работу, т. е. программа при этом вы. полняет команду ассер!. Она состоит всего из одного дизъюнкта: о 11 к)) Е(х) = Х Уо(1"!)'1' ! г!' 1=! Этим завершается построение Е(х). Прежде всего заметим, что это построение требует только полиномиального — относительно (х! — количества времени. Это следует из того факта, что общая длина формулы Р (число вхождений литералов, умноженное на длину индексов этих литералов в формуле Е) не превосходи) 0(р'()х!) !од р()х!).
Поэтому, чтобы показать, что это построение является полиномиальным преобразованием задачи А в задачу ВЫПОЛНИМОСТЬ, остается доказать Утверждение. Формула Е (х) выполнима в том и только в том случае, если х является индивидуальной задачей задачи А с ответом да. Для доказательства необходимости предположим, что Е(х) выполнима. Тогда все формулы Г)(х), 5(х), ))"(х) и Е(х) выполнимы при одном и )ом же наборе значении истинности !. Так как на наборе ! выполняется Г)(х), то для всех 1' и ) ровно одна переменная хы, должна быть истинной; пусть это означает, что !'-я ячейка в момент времени 1 содержи) о. Кроме того, для всех 1 ровно одна из переменных д))1 истинна; пусть это означает, что в момент времени 1 обозревается )ия позиция строки и выполняется операгор !.
НаКОНЕЦ, НИКаКая ПЕрЕМЕННая ВИда д)„1 ИЛИ у), Оокц+),1 НЕ МОжс~ быть истинной, что означает, что головка никогда не сходит со строки. Таким образом, набор значений истинности ) описывает неко. топую последовательность строк, положений головки и команд. Покажем, что эта последовательность образует правильное принимая)щее вычисление для алгоритма 1( при входе х9с(х) для некотои го уд~)стовереиия с(х), Так как!)(х! гакже должно выполняться иа наборе ), то ука. заииая последовательность начинается корректно: вначале первые )х)+! мест заняты правильной строкой х9 и при выполнении пер.
вой команды обозревается первый символ строки х. То) факт, что (Г)(х) )акже выполняется на наборе (, означает, ч)о последовательность изменяется согласно правилам выполнения !б.б. Другов гч'Р-иоаиыг оадачиг КЛОКА и ЗК 369 алгоритма Х Наконец, Е(х) выполняется на наборе 1 только в том случае, если алгоритм оканчивается последней принимающей командой.
Следовательно, если формула Р(х) выполнима, то существует строка с(х) подходящей длины, такая, что и1 принимает х1с(х); поэтому х является индивидуальной задачей задачи А с ответом да. Для доказательства достаточности допустим, что х — индивидуальная задача с ответом да. Тогда существует такая строка с(х) длины р()х)) — )х( — 1, что г принимает х$с(х). Это означает, что существует последовательность Р(1х1) (с первой строкой хчс(х)), номеров команд и обозреваемых позиций, допустимая для алгоритма и1 и оканчивающаяся принятием строки х$с(х), Эта последовательность непосредственно определяет набор значений истинности 1, который с необходимостью выполняет Р(х). Этим завершается доказательство утверждения.
Рассматриваемое утверждение показывает, что Р(х) является индивидуальной задачей задачи ВЫПОЛНИМОСТЬ с ответом да тогда и только тогда, когда х является индивидуальной задачей задачи А с ответом да. Поэтому описанное преобразование является полиномиальиым преобразованием задачи А в задачу ВЫПОЛНИМОСТЬ. Так как в качестве А была выбрана произвольная задача из МР, то теорема доказана. ( ) Следствие.
Задача ЦЛП )йР-паина. Доказательство. В примере 15.8 показано, что задача ЦЛП содержится в 1)Р. Для доказательства КГР-полноты этой задачи досзаточно вспомнить полиномиальное преобразование задачи ВЫПОЛНИМОСТЬ в задачу ЦЛП, описанное в примере !ЗА, д 1$.6 Другие УР-полные задачи: КЛИКА и ЗК Сейчас мы установим, что еще ряд задач из 14Р являются й)Р- полными, для чего будем показывать, что в рассматриваемую задачу преобразуется задача ВЫПОЛНИМОСТЬ или какая-нибудь другая задача, гч'Р-полнота которой уже доказана. Применнемая техника доказательства интересна сама по себе, и мы будем отмечать некоторые основные элементы методологии. Частный случай задачи ВЫПОЛНИМОСТЬ, в котором каждый дизъюнкт может содержать не более двух литералов, может быть решен за линейное время (см. задачу 6).
ОднаК~, как мы сейчас покажем, если допускаются три литерала в каждом дизъюнкте, то соответствующая задача, называемая З-ВЫПОЛНИМОСТЬ, остается такой же трудной, как и сама задача ВЫПОЛНИМОСТЬ. Гл. 15. 7»*Р.полные эадачи 370 Теорема 13.2. Задача 3-ВЫПОЛНИМОСТЬ ИР-полна. Доказательство. Так как задача 3-ВЫПОЛНИМОСТЬ является частным случаем задачи ВЫПОЛНИМОСТЬ, то она входит в )УР. Для доказательства ФР-полноты покажем, что ВЪ|ПОЛНИМОСТЬ полиномиально преобразуется в 3-ВЫПОЛНИМОСТЬ. Рассмотрим произвольную формулу Р, состоящую из дизъюнктов С„..., С . Построим новую формулу Р' с тремя литералами в каждом дизьюнкте, такую, что Р' выполнима тогда и только тогда, когда выполнима Р. Просмотрим дизъюнкты формулы Р по очереди и заменим каждый дизъюнкт С; эквивалентным множеством дизъюнктов, каждый из которых содержит три личерала, Рассмотрим три случая.
1. Если С; содержит ~ри литерала, то ничего не делаем. 2, Если С, содержит более трех литералов, например С,=(1,+ -)-Х,+... +)»), й)3, то заменим С; на )е — 2 дизъюнктов (Х,+)»+ +х ) (х»+)»+х») (х»+1 +х») ... (х» +1» +)»), где хь ..., х»» — новые переменные.
Нетрудно понять, что набор этих новых дизъюнктов выполним тогда и только тогда, когда выполним дизь. юнкт Сь 3, Если С,=-), заменяем С, на ).+у+г, а если С,=Х.+)', заменяем его на ).-)-)'+у. Затем к эгой формуле добавляем дизъюнкты (я+а+(5) (я+а+ Р) (г+а+р) (я+а+3) (у+ а+Я (у+ х+()) (у+а+()) (у+ а+ Я, где у, г, а и () — новые переменные. Такое добавление приводит к тому, что переменные г и у будут принимать значения ложь в любом наборе значений истинности, выполняющем Р', поэтому дизъюнкты Х и е.+Х' эквивалентны заменяемым нх дизъюнктам.
Таким образом, мы избавились от всех дизъюнктов, число литералов в которых отлично от трех, и, кроме того, показали, что полученная в результате формула Р' выполнима тогда и только тогда, когда выполнима Р. Построение формулы Р' можно, очевидно, выполнизь за полиномиальное время.
Следовательно, описанное нами преобразование является полиномиальным преобразованием задачи ВЫПОЛНИМОСТЬ в задачу 3-ВЫПОЛНИМОСТЬ. Поэтому задача 3-ВЫПОЛНИМОСТЬ ФР-полна. | | Воспользуемся Л'Р-полнотой задачи 3-ВЫПОЛНИМОСТЬ для доказательства следующей теоремы. Теорема !3.3. Задача КЛИКА НР-полна. Доказательство, Мы уже знаем, что КЛИКА Е НР. Поэтому достаточно показа~ь, что 3-ВЫПОЛНИМОСТЬ полиномиально преобразуется в задачу КЛИКА. По произвольной булевой формуле 1б.б. Другиг 11Р-полнив задачи: КЛНКА и ЗК 371 Е с тремя литералами в каждом дизъюнкге мы построим граф 6= =($', Е) и целое число й, такие, что в 6 имеется клика размера й тогда и только тогда, когда Г выполнима, Введем сначала некоторые термины и обозначения, В частичном наборе значений истинности 1 значения истина и ложь приписыва.
ются только некоторым переменным; остальным переменным сопо- ставляется значение истинности 1(х) = — д, особое значение, означаю- щее неопределенноопь. В качестве множества переменных зафик- сируем х„..., х„. Частичный набор значений истинности будем представлять последовательностью нулей, единиц и символовд, Так 1=с(01г(0(п=5) — это частичный набор значений истинности, в ко- тором 1(х,)=ложь, 1(х,)=истина, 1(х,)=ложь и остальные значения не определены.
Два частичных набора значений истинности 1 и 1' называются совместимыми, если для всех переменных х, таких, что 1(х)Фс( и 1'(х)Фд, выполняется равенство 1(х)=1'(х). Пусть С„..., С вЂ” дизъюнкты формулы Е. Множество вершин )г будет содержат семь вершин для каждого дизъюнкта С„а именно вершины 16, 1=1, ..., 7. Эти вершины можно рассматривать как частичные наборы значений истинности, в которых определенные значения приписаны только трем переменным, содержащимся в Сь Из восьми таких частичных наборов значений истинности мы опускаем только один набор, в котором всем трем литералам дизь- юнкта С; присваивается значение ложь. Это проиллюстрировано на рис. !5.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
