(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) ((см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010).pdf), страница 14

Нетрудно видеть, что 3-ВЫПе NP. Этоследует из того, что недетерминированному алгоритмунеобходимо угадать лишь набор значений истинностипеременных задачи и проверить за полиномиальное время,будут ли при таком наборе значений истинности выполнятьсявсе заданные трехлитеральные дизъюнкции.Сведем задачу ВЫП к задаче 3-ВЫП. Пусть U = { uJt и?,... , м„}-множество переменных и С={с1,с2, ...

,с„,} - про­извольный набор дизъюнкций, определяющий произвольнуюиндивидуальную задачу из ВЫП. Построим набор С'трехлитеральных дизъюнкций на некотором множествепеременных U', такой, что С’ выполним тогда и только тогда,когда выполним С.Набор С будет строиться путем замены каждойотдельной дизъюнкции с, е С «эквивалентным» наборомтрехлитеральных дизъюнкций С, на множестве U исходныхпеременных и множестве U\ некоторых дополнительныхпеременных, причем переменные из U \ будут использоватьсятолько в дизъюнкциях из С’,. Другими словами,иТаким образом, нужно показать, как, исходя из с „ можнопостроить С / и U).Пусть с, задается множеством {zj,Z2, ...,zk}, где z, — ли­тералы на множестве U.

Способ образования С) и U',- зависитот значения к.Случай L й = 1 , Тогдаyj},Случай 2, А = 2. ТогдаС/ — {{гн %Случай 3, к — 3. Тогда Щ *=■($, С| =Случай 4. /е > 3. Тогда /7^ = {?/':{z \> zp #)}}*—Для доказательства того, что здесь в самом деле имеетместо сводимость, необходимо показать, что набордизъюнкций С выполним тогда и только тогда, когдавыполним набор дизъюнкций С. Предположим вначале, что t:{/—>{T,F} есть набор значений истинности, выполняющий С.Покажем, что t может быть продолжен до набора значенийистинности t': If—»{T,F}, который выполняет С'. Посколькупеременные в множестве U'\U делятся на группы 1Г, и так какпеременные в каждой группе £/', входят только в дизъюнкции,принадлежащие С'„ то достаточно показать, как t может бытьпродолжен на каждое множество U', отдельно, и в каждомслучае нужно проверить, что выполняются все дизъюнкции всоответствующем множестве СЭто можно сделать следующим образом.

Если U ’,построены, как в случае 1 или 2, то дизъюнкции из С”, ужевыполнены с помощью t , поэтому t может быть продолжен наU ) произвольно, например, если положить t'(y) - Т для всехуеU). Если U) построено, как в случае 3, то U) пусто иединственная дизъюнкция в С ) уже выполнена с помощью /.Остается только случай 4, который соответствует дизъюнкции{zj, z2, ... , z,.} из С, причем к > 3. Поскольку t - выполняющийнабор значений истинности для С, то найдется такое целое /,что Z/ при t принимает значение истина. Если /=1 или 2, тополагаем t(yi) = F, 1< /<к-3. Если / = к-1 или к , то полагаемt'(y'i)= F, l<i<k-3. В противном случае полагаем t (у j) - F приi< i < 1-2. Легко проверить, что такой набор значенийистинности обеспечит выполнение всех дизъюнкций в С),поэтому t' выполняет все дизъюнкции из С. Обратно, если t' некоторый, выполняющий набор значений истинности для С',то легко проверить, что ограничение t' на переменные из Uдолжно быть выполняющим набором значений истинностидля С.

Таким образом, С выполним тогда и только тогда,когда выполним С.Для того чтобы убедиться, что эта сводимостьполиномиальная,достаточнозаметить,чточислотрехлитеральных дизъюнкций в С ограничено полиномом оттп. Следовательно, размер индивидуальной задачи 3-ВЫПограничен сверху некоторым полиномом от размерасоответствующей задачи ВЫП, а так как все деталипостроения сводимости очевидны, то читателю будетнетрудно проверить,что эта сводимость являетсяполиномиальной.Ограниченная структура задачи 3-ВЫП делает ее гораздоболее полезной при доказательстве результатов об NP-полнотепо сравнению с задачей ВЫП. Любое доказательство,основанное на задаче ВЫП (кроме только что приведенного),может быть легко перестроено в доказательство, основанноена 3-ВЫП, даже без изменения функции, осуществляющейсводимость.

На самом деле дополнительное условие о том, чтовсе дизъюнкции имеют одинаковую длину, часто можетупростить сводимость, которую нужно построить, и темсамым облегчить ее отыскание. Более того, очень малая длинадизъюнкций позволяет использовать сводимости, которыевообще не могли бы быть построены для индивидуальныхзадач с дизъюнкциями большей длины. Это наводит на мысль,что было бы еще лучше, если бы удалось показать, чтоаналогичнаязадача2-ВЫПОЛНИМОСТЬ(каждаядизъюнкция содержит ровно два литерала) является NPполной. Однако 2-ВЫП может быть решена, например,методом «резолюций» за время, ограниченное полиномом отпроизведения числа дизъюнкций и числа переменныхзаданной индивидуальной задачи и, следовательно, принад­лежит классу Р (для других доказательств полиномиальности2-ВЫП см. (4), стр.

57-58 или (5), Теорема 5.2, стр.30-32;также, для доказательства NP-полноты задачи 3-ВЫП см. (4),стр. 55-56 или (5), стр. 32-33).ТРЁХМЕРНОЕ СОЧЕТАНИЕЗадача ТРЕХМЕРНОЕ СОЧЕТАНИЕ (3-С) обобщает сле­дующую известную задачу о «бракосочетании»: имеется пхолостых мужчин и п незамужних женщин, а также списоквсех пар мужчин и женщин, согласных вступить в брак друг сдругом; можно ли осуществить п бракосочетаний так, чтобыкаждый получил бы приемлемого супруга (или супругу),причемникто не должен вступать в брак дважды?Аналогичным образом в задаче ТРЕХМЕРНОЕ СОЧЕТАНИЕмножества W, X и Y соответствуют трем различным «полам»,а каждая тройка из М отвечает «трехмерному сочетанию»,приемлемому для всех трех участников. В то время как задача3-С является NP-полной, обычная задача о бракосочетанииможет быть решена за полиномиальное время.Теорема5.2.

Задача ТРЕХМЕРНОЕ СОЧЕТАНИЕявляется NP -полной.Доказательство. Легко видеть, что З-Се NP. Это следуетиз того, что недетерминированному алгоритму нужно толькоугадать подмножество в М, состоящее из ^=|И^|=р^)=|У) троек, иза полиномиальное время проверить, что любые две изугаданных троек отличаются по всем координатам.Сведем задачу 3-ВЫП к задаче 3-С. Пусть U = {ult и2, ...,ип} - множество переменных и C={cfi, с2, ..., с„,} - множестводизъюнкций произвольной индивидуальной задачи из 3-ВЫП.Нужно построить непересекающиеся множества W, X, Y иM s W X X X Y , такие, что |Ж|=|А|=|У1 и М содержитпаросочетание в том и только в том случае, когда С выпол­нима.Искомое множество упорядоченных троек М будетразбито на три различных класса в соответствии с ихфункциональным назначением: «набор значений истинности иразвертка», «проверка выполнения» и «достройка».Тройки, входящие в первый класс, разбиваются нагруппы (компоненты), каждая из которых соответствует однойпеременной us U, а ее строение зависит от общего числа тдизъюнкций в С.

Строение этой компоненты для случая т=4показано на рис. 5.2. В общем случае каждая такаякомпонента, соответствующая переменной и, , включает«внутренние» элементы a,[j] е X и b,\j] е Y, l<j<m, которые небудут входить ни в какую тропку вне этой компоненты, и«внешние» элементы и,[/'], /7,[/]е W, 1е /< т , которые будутвходить в другие тройки. Образующие эту компоненту тройкимогут быть подразделены на два множества:П " { ( “Л/]* Д/Ш> М Л ):= {(и/ [Л» « Л /“К ) . МП): 1 < /• < • « } [J[]{(«< М .

й([ 1 ], Ь,|т])}.Так как внутренние элементыМ /Ь 1т} могутвходить только в тройки, принадлежащие множеству Т;=Т1; иТ£, то легко видеть, что любое трехмерное сочетание М'должно иметь ровно т троек из Tj, а именно либо все тройкииз Т\ , либо все тройки из Т£. Следовательно, можно считать,что компонента из Т; приводит к тому, что трехмерноесочетание индуцирует присвоение переменной м, значения«истина» или «ложь». Таким образом, трёхмерное сочетаниеМ 'сМ оп ределяет набор значений истинности на множествеU, при этом переменная и, принимает значение «истина» тогдаи только тогда, когда М ’пТ; = Т*;Каждая компонента множества М, предназначенная дляпроверки выполнимости, соответствует одной дизъюнкции с;еС. Такая компонента содержит только два «внутренних»элементаX и $.?[/'] е Y, а также «внешние» элементы измножества {u\j\, и,\ 1</<«}, выбираемые в зависимости оттого, какие, литералы содержатся в дизъюнкции с(.Множество троек, образующих эту компоненту,определяются следующим образом:С/— {(iij[j),s2[/]): й( e Cj) j j {(«;[/]>^W ):Итак, любое трехмерное сочетание Л/ t М должносодержать ровно одну тройку из Cj .

Но это условие можетбыть выполнено только в том случае, если для некотороголитерала и,е«/[/])с, (или /г,-ес,) элемент «,-[/] (соответственнод[3]Ри с 5 .2 К ом п о н ен таТ„ зад аю щ аязначения и сти н н ости при т = 4 (ниж ниеи н дексы п ер ем ен н ы х для п р осто ты о пущ ен ы ). Д о лж н о б ы т ь вы б ран о либом н о ж еств оТ!(за ш тр и хован н о е м н о ж ес тв о ), ли бо 7} (н езаш тр и х ован н о ем н о ж ес тв о ), при э т о м о ст а ю т ся Н Е П О К Р Ы Т Ы М И (т .е н е объедин ён н ы м и втрой ки ) либо в с е K ,[j], либо в с еи,-Ц] со о тв етствен н о .не войдет ни в одну из троек множества Т, п М', а это будет,иметь место тогда и только тогда; когда набор значенийистинности, определяемый множеством М’, выполняетдизъюнкцию с,.Построение нужной индивидуальной задачи из 3-С будетзакончено после описания одной большой компоненты«достройки» G. Эта компонента включает внешние элементыgifk]e X, g 2[k]e Y, \<к<тп(п— 1), а также внешние элементывида !/,[/'] (или я?,- [/] из множества W.

Компонента G состоитиз следующего множества троек:Таким образом, каждая пара gi[k], g 2[k] должна войти втрехмерное сочетание только с одним из элементов «,■[/] илиы ,■[/], не попавших в тройки из М ‘ \ G. Имеется ровно т(п—1)таких «непокрытых» внешних элементов, и структуракомпоненты G обеспечивает, что они всегда могут бытьпокрыты с помощью выбора соответствующего подмножестваМ' ел G, Следовательно, компонента G гарантирует, что, еслидля некоторого подмножества из M\G выполняются всеограничения, налагаемые компонентами набора значенийистинности, тогда это подмножество может быть дополненодо трехмерного сочетания в М.Резюмируя сказанное, положим:Г=(и,Ш.