(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) (1186152), страница 11
Текст из файла (страница 11)
авремя работы только что построенной программы, как нетрудно видеть, ограничено функцией 0(pi(\х\)+ р 2(\х\)),которая является полиномом от |х|.Если П] и П2 - задачи распознавания, a et и е2 - их схемыкодирования, то будем писать П 1 ЖП2 (относительно заданныхсхем кодирования),еслисуществует полиномиальнаясводимость языка Ц П ье/] к L[П2,е2]. Когда будет действоватьстандартное предположение о разумности используемых схемкодирования, упоминание о конкретных схемах кодирования,как обычно, будет опускаться. Таким образом, на уровне задачполиномиальная сводимость задачи распознавания FIj к задачераспознавания П2 означает наличие функции f.
D „ j — * D „ 2 ,удовлетворяющей двум условиям:( 1 ) / вычисляется полиномиальным алгоритмом;(2 ) для всех 1 е Д „ 1 е Г„/, тогда и только тогда, когдаД 1 ) е Уп2.Чтобыполучитьконкретноепредставлениеосодержательном смысле этого определения, рассмотримпример. Пусть G =(V,E) - граф с множеством вершин V имножеством ребер Е. Простым циклом в G называется такаяпоследовательность < vy, v2...... vk > различных вершин из V,что {v,, v,>/}g Е, 1< i <к, и {vk,vi}e. Е.Гамильтоновым циклом в G называется простой цикл,содержащий все вершины графа G.
Задача ГАМИЛЬТОНОВЦИКЛ определяется следующим образом:ГАМИЛЬТОНОВ ЦИКЛУСЛОВИЕ. Задан граф G=(V, Е).ВОПРОС. Верно ли, что G содержит гамильтонов цикл?Читатель, несомненно, заметил определенную связьмеждуэтойзадачейизадачейраспознаванияКОММИВОЯЖЕР. Покажем, что ГАМИЛЬТОНОВ ЦИКЛ(ГЦ) сводится к КОММИВОЯЖЕРУ (КМ). Для этоготребуется указать функцию f которая отображает каждуюиндивидуальную задачу из ГЦ в соответствующуюиндивидуальную задачу из КМ и удовлетворяет двумусловиям, которые требуются от полиномиальной сводимости.Функция/ определяется очень просто. Пусть G = (V, Е),\V\=m означает фиксированную индивидуальную задачу из ГЦ.Соответствующая задача из КМ строится так: множествогородов С совпадает с Г и для любых двух городов v,, v, е Срасстояние d(v„ vj между ними полагаем равным 1 , если {v,,v,}e Е и 2 в противном случае. Граница В для длиныискомогомаршрутаберетсяравнойт.КаждойиндивидуальнойзадачеизГЦмысопоставляеминдивидуальную задачу из КМ.
Каждой вершине графасопоставляем некоторый город, т.е. число городов равночислу вершин графа т и между ними имеется взаимнооднозначное соответствие. Расстояние между i'-ым и у-ымгородами равно 1 , если они соединены ребром в исходномграфе и равно 2 в противном случае.Легко показать (на неформальном уровне), что этафункция / осуществляет сводимость и может быть вычисленаза полиномиальное время.
Для вычисления т(т—1)/2расстояний d(v,,Vj) необходимо лишь выяснить, принадлежитли (v, , V,) множеству Е или нет. Поэтому первое требованиеполиномиальности сводимости выполнено. Для проверкивторого требования необходимо показать, что G содержитгамильтонов цикл тогда и только тогда, когда в f(G) имеетсяпроходящий через все города маршрут длины, непревосходящей В.
Вначале допустим, что <V], v2, ..., v,„> гамильтонов цикл в G. Тогда <V], v2, ..., v,„> - маршрут в f(G), аего длина равна т (т = В), так как расстояние между любымисоседними городами маршрута равно 1 , поскольку оносоответствует ребру в G. Наоборот, предположим, что (v,,v2....v,„) - маршрут в f(G), длина которого не превосходит В.Поскольку расстояние между любыми двумя городами в f(G)равно либо 1 , либо 2 и при вычислении длины маршрутасуммируется ровно т таких расстояний, то из равенства В = тследует, что расстояние между каждой парой соседнихгородов в маршруте равно 1.
По определению f(G), отсюдаследует, что (v.. v, ,-; ), 1 < / < т и ( v,„, v2) являются ребрамиграфа G и, следовательно, < vj, v2 , ... , v,„> - гамильтоновцикл в G.Таким образом, мы доказали, что ГЦ°сКМ . Хотя этодоказательство гораздо проще многих доказательств, которыебудут рассмотрены в дальнейшем, оно содержит всесущественные элементы доказательства полиномиальнойсводимости и на неформальном уровне может служитьмоделью для построения таких доказательств.Значение Леммы 4Л выше для задач распознаваниятеперь может быть проиллюстрировано на примересводимости ГЦКМ. По существу, мы пришли кследующему заключению: если задача КОММИВОЯЖЕРможет быть решена полиномиальным алгоритмом, то этотфакт верен и для задачи ГАМИЛЬТОНОВ ЦИКЛ, а если ГЦ труднорешаемая задача, то и КМ также труднорешаемаязадача.Такимобразом,Лемма4Лпозволяетинтерпретировать сводимость ГК ос ц 2 как утверждение, чтозадача П2 «не проще» задачи П^.Отношение полиномиальной сводимости особенноудобно, поскольку оно является транзитивным.
Этоустанавливает следующая лемма.Лемма 4.2. Если L] о с Ь2 и Ь2Ь2, то Lj ос Г,.Доказательство. Пусть Eh £ 2, Е3 - алфавиты языков Lj,L2 и L3 соответственно, функция / г: £*/—>£*2 реализуетполиномиальную сводимость L/ к 12, а / 2: Е*2-+£*з полиномиальную сводимость 12 к L3.
Тогда функция fЕ*1~+£*з, которая для всех хе Г* определяется соотношениемЯх) - КНУХ*))> реализует искомую сводимость языка Г; к языкуЬ3. В самом деле,Дх)е Ь3 тогда и только тогда, когда хе Lh авычислимость / за полиномиальное время получается спомощьюрассуждений,аналогичныхрассуждениям,использованным при доказательстве Леммы 4.1.Теперь можно сказать, что языки Lj и L2 (соответственнозадачи распознавания П] и П2) полиномиально эквивалентны,если они сводятся друг к другу, т. е. Ь^-Ь-з и L2^ L ] (имеетместо сводимость П) ^ П2 и Пг0^ П 1).
Лемма 4.2 утверждает,что это отношение является отношением эквивалентности, атакже, что отношениеопределяет частичное упорядочениевозникающих классов эквивалентности языков (задач распознавания). На самом деле класс Р - это наименьшийотносительноэтогочастичногопорядкаклассэквивалентности и с вычислительной точки зрения его можнорассматривать как класс самых легких языков (задачраспознавания). Класс NP-полных языков (задач) дает намдругой класс эквивалентности, который характеризуется тем,что он содержит самые трудные языки (задачи распознавания)из NP.Рис.
4 1 Уточнённая картина класса NP,Язык L называется NP-полным, если Le NP и любой другой язык L'e NP сводится к языку L. Говоря неформально,задача распознавания П называется NP-полной, если П е NP илюбая другая задача распознавания Пе NP сводится к П.Таким образом, Лемма 4.1 позволяет отождествить NPполные задачи с самыми трудными задачами из NP. Еслихотя бы одна NP-полная задача может быть решена заполиномиальное время, то и все задачи из NP также могутбыть решены за полиномиальное время.
Если хотя бы одназадача из NP труднорешаема, то и все NP-полные задачитруднорешаемы. Следовательно, любая NP-полная задача Побладает свойством, котороесформулировано в началенастоящего раздела: если P^NP, то П е NP\P. Точнее, Пе Ртогда и только тогда, когда Р = NP.В предположении P*NP можно дать более точнуюкартину класса NP, см. рисунок выше.(рис. 4.1). Заметим, чтоNP не просто разделяется на две области: класс Р и класс NPполных задач. Если Р отличен от NP, то должны существоватьзадачи из NP, неразрешимые за полиномиальное время и неявляющиеся NP-полными.Мы будем интересоваться в основном NP-полнымизадачами.
Хотя в начале и говорилось, что имеются простыеметоды доказательства NP-полноты задач, требования,описанные нами, как будто свидетельствуют об обратном.Нужно доказать, что любая задача из NP сводится кнекоторому кандидату на NP-полную задачу. Совершенно неясно, как это можно было бы доказать.
Не очевидно даже, чтосуществует хотя бы одна NP-полная задача.Следующая лемма, которая немедленно следует изопределений и транзитивности отношения с< показывает, чтовопрос сильно упростился бы, если бы была известна покрайней мере одна NP-полная задача.Лемма 4.3. Если Ь2 и Ь2 принадлежат классу NP, Lt это NP-полный язык и L j ^ Ь2, то Ь2 также NP-полный язык.Доказательство. Так как Ь2е NP, то достаточнопоказать, что для всякого L’e NP L' сводится к Ь2. Рассмотримлюбой язык L'e NP. Так как Lj - NP-полный-язык, то L' сводится к Lj. В силу транзитивности отношениясх- , изсводимости L] CsCL2 следует L,fX-L2.На уровне задач распознавания Лемма 4.3 указываетпростой путь доказательства NP-полноты новой задачи П,если известна хотя бы одна NP-полная задача. Для того чтобыдоказать NP-полноту задачи П, достаточно показать, что:1.
П е NP.2. Какая-то одна известная NP-полная задача П' сводится к П.Но прежде чем можно будет воспользоваться этим методом доказательства, необходимо найти некоторуюисходную NP-полную задачу. Такую задачу дает намфундаментальная теорема Кука, которую мы сформулируем идокажем в следующем разделе.ТЕОРЕМА КУКАЧесть быть первой NP-полной задачей выпала на долюзадачи распознавания из булевской логики, задачи, которуюобычно называют ВЫПОЛНИМОСТЬ (сокращенно ВЫП).Термины, использующиеся для ее описания, определяютсяследующим образом.Пусть U - {и, , и2, ...
, ит } — множество булевских переменных. Под набором значений истинности на множестве Vбудем понимать функцию I: U—+{T, F}. Если /(u) = Т, то будемговорить, что и принимает значение «истина» относительно t;если t(u) =F, то будем говорить, что и принимает значение«ложь». Если и - переменная из U, то и и гг назовем литералами из U. Литерал и принимает значение «истина»относительно t в том и только в том случае, если переменная ипринимает значение «истина» относительно t; литерал гг.принимает значение истина в том и только в том случае, еслипеременная и принимает значение «ложь».Дизъюнкцией над U назовем множество литералов над Цнапример {uit /г ;, ин\. Она представляет дизъюнкцию этихлитералов и называется выполненной при некотором наборезначений истинности тогда и только тогда, когда прирассматриваемом наборе значений истинности хотя бы одиниз ее членов принимает значение «истина».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
