dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 97
Текст из файла (страница 97)
В этой оценке времени работы учитывается тот факт, что необходимо не только решить итоговый экземпляр P2, но и получить его. И вновь возможно, что P2 принадлежит P, а P1 — нет.Правильное ограничение, которое необходимо наложить на преобразование P1 в P2,состоит в том, что время его выполнения должно полиномиально зависеть от размеравходных данных. Отметим, что если при входе длины m преобразование занимает времяO(mj), то длина выходного экземпляра P2 не может превышать числа совершенных шагов, т.е.
она не больше cmj, где c — некоторая константа. Теперь можно доказать, что если P2 принадлежит P, то и P1 принадлежит P.Для доказательства предположим, что принадлежность цепочки длины n к P2 можновыяснить за время O(nk). Тогда вопрос о принадлежности P1 цепочки длины m можнорешить за время O(mj + (cmj)k); слагаемое mj учитывает время преобразования, а (cmj)k —время выяснения, является ли результат экземпляром P2. Упрощая выражение, видим,что P1 может быть решена за время O(mj + cmjk). Поскольку c, j и k — константы, этовремя зависит от m полиномиально, и, следовательно, P1 принадлежит P.Итак, в теории труднорешаемости используются только полиномиальные сведения(сведения за полиномиальное время).
Сведение P1 к P2 является полиномиальным, еслионо занимает время, полиномиальное по длине входного экземпляра P1. Как следствие,длина выходного экземпляра P2 будет полиномиальной по длине экземпляра P1.10.1.6. NP-ïîëíûå ïðîáëåìûТеперь познакомимся с группой проблем, которые являются наиболее известнымикандидатами на то, чтобы принадлежать NP, но не принадлежать P. Пусть L — язык(проблема) из класса NP. Говорят, что L является NP-полным, если для него справедливы следующие утверждения.1.L принадлежит NP.2.Для всякого языка L' из NP существует полиномиальное сведение L' к L.432Стр.
432ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛКак мы увидим, примером NP-полной проблемы является проблема коммивояжера(см. раздел 10.1.4). Предполагается, что P ≠ NP, и, в частности, что все NP-полные проблемы содержатся в NP – P, поэтому доказательство NP-полноты проблемы можно рассматривать как свидетельство того, что она не принадлежит P.Вначале докажем NP-полноту так называемой проблемы выполнимости булевойформулы (ВЫП), показав, что язык всякой НМТ с полиномиальным временем полиномиально сводится к ВЫП. Имея в распоряжении некоторые NP-полные проблемы, можно доказать NP-полноту еще одной, новой проблемы посредством полиномиального сведения к ней одной из известных проблем. Следующая теорема объясняет, почему такоесведение доказывает, что новая проблема является NP-полной.Теорема 10.4.
Если проблема P1 является NP-полной, и существует полиномиальноесведение P1 к P2, то проблема P2 также NP-полна.Доказательство. Нужно показать, что всякий язык L из NP полиномиально сводитсяк P2. Мы знаем, что существует полиномиальное сведение L к P1; это сведение занимаетнекоторое полиномиальное время p(n). Поэтому цепочка w из L длиной n преобразуетсяв цепочку x из P1, длина которой не превосходит p(n).Мы также знаем, что существует полиномиальное сведение P1 к P2; пусть это сведениезанимает полиномиальное время q(m).
Тогда это сведение преобразует x в некоторую цепочку y из P2, за время, не превосходящее q(p(n)). Таким образом, преобразование w в y занимает времени не более p(n) + q(p(n)), которое является полиномиальным. Следовательно,L полиномиально сводим к P2. Поскольку L — произвольный язык из NP, то мы показали,что все проблемы класса NP полиномиально сводятся к P2, т.е. P2 является NP-полной.
NP-òðóäíûå ïðîáëåìûНекоторые проблемы L трудны настолько, что, хотя и можно доказать, что для них выполняется условие 2 из определения NP-полноты (всякий язык из NP сводится к L заполиномиальное время), условие 1 — что L принадлежит NP — мы доказать не можем.Если это так, то L называется NP-трудной. До сих пор в отношении проблем, требующих для решения экспоненциального времени, использовался нестрогий термин“труднорешаемая”. Вообще говоря, термин “труднорешаемая” в значении “NP-трудная”использовать можно, хотя могут существовать проблемы, требующие экспоненциального времени, несмотря на то, что в строгом смысле они не являются NP-трудными.Для доказательства NP-трудности проблемы L достаточно показать высокую вероятность того, что L требует экспоненциального или большего времени.
Однако если Lне принадлежит классу NP, то ее очевидная трудность никак не может служить подтверждением того, что все NP-полные проблемы трудны, т.е. может выясниться, чтоP = NP, но при этом L все равно требует экспоненциального времени.10.1. ÊËÀÑÑÛ P È NPСтр.
433433Есть еще одна, более важная, теорема, которую нужно доказать для NP-полных проблем: если любая из них принадлежит P, то весь класс NP содержится в P. Но мы твердоверим, что в NP содержится много проблем, не принадлежащих P. Таким образом, доказательство NP-полноты проблемы мы считаем равносильным доказательству того, чтоу нее нет алгоритма решения с полиномиальным временем, и поэтому она не имеет хорошего компьютерного решения.Теорема 10.5.
Если некоторая NP-полная проблема P принадлежит P, то P = NP.Доказательство. Предположим, что P одновременно и NP-полна, и принадлежит P.Тогда любой язык L из NP полиномиально сводится к P. Если P принадлежит P, то и Lпринадлежит P (см. раздел 10.1.5). 10.1.7. Óïðàæíåíèÿ ê ðàçäåëó 10.110.1.1. Каким будет ОДМВ для графа на рис 10.1, если вес его ребер изменить следующим образом:а) (∗) вес 10 ребра (1, 3) изменить на 25;б) изменить вес ребра (2, 4) на 16.Àëüòåðíàòèâíûå îïðåäåëåíèÿ NP-ïîëíîòûКонечной целью изучения NP-полноты является теорема 10.5, т.е. поиск проблем P,принадлежность которых классу P влечет равенство P = NP. Определение “NPполноты”, использованное здесь, часто называется полнотой по Карпу, посколькуоно впервые было использовано Р.
Карпом в фундаментальной работе на данную тему. Этому определению соответствует любая проблема, предположительно удовлетворяющая условиям теоремы 10.5.Однако существуют другие, более широкие понятия NP-полноты, для которых теорема 10.5 также справедлива. Например, С. Кук в своей первой работе, посвященнойданному предмету, дал следующее определение “NP-полноты” проблемы P. Проблему P он назвал NP-полной, если, имея для проблемы P оракул — механизм, которыйза единицу времени определяет, принадлежит ли данная цепочка P, — можно распознать всякий язык из NP за полиномиальное время.
Этот тип NP-полноты называютполнотой по Куку. В некотором смысле, полнота по Карпу есть частный случай этойполноты, когда оракулу задается лишь один вопрос. Однако полнота по Куку допускает отрицание ответа. Можно, например, задать оракулу некоторый вопрос, а в качестве ответа взять противоположное тому, что он ответит. Согласно определению полноты по Куку, дополнение NP-полной проблемы также является NP-полной проблемой. Используя же более узкое определение полноты по Карпу, можно указатьважное отличие NP-полных проблем от их дополнений. Это делается в разделе 11.1.434Стр.
434ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛ10.1.2. Каким будет гамильтонов цикл минимального веса для графа на рис. 10.1, если внего добавить ребро с весом 19, соединяющее узлы 1 и 4?10.1.3. (∗!) Предположим, что существует NP-полная проблема с детерминированнымрешением, занимающим время O( nlog n ). Заметим, что эта функция лежит меж2ду полиномами и экспонентами и не принадлежит ни одному из этих классовфункций. Что можно сказать о времени, необходимом для решения произвольной проблемы из NP?10.1.4.
(!!) Рассмотрим графы, узлами которых являются узлы целочисленной решеткив n-мерном кубе со стороной длины m, т.е. векторы (i1, i2, …, in), где каждое ijнаходится в диапазоне от 1 до m (или от 0 до m – 1). Ребро между двумя узламисуществует тогда и только тогда, когда они различаются на единицу ровно поодной координате. Например, вариант n = 2 и m = 2 представляет собой квадрат,n = 3 и m = 2 — куб, а n = 2 и m = 3 — граф, изображенный на рис. 10.3.
Некоторые из этих графов имеют гамильтонов цикл, некоторые — нет. Например,квадрат имеет такой цикл. Куб — тоже, хотя это и не очевидно; примером является цикл (0, 0, 0), (0, 0, 1), (0, 1, 1), (0, 1, 0), (1, 1, 0), (1, 1, 1), (1, 0, 1), (1, 0, 0) иснова (0, 0, 0). Граф на рис. 10.3 гамильтонова цикла не имеет.Рис. 10.3. Граф, соответствующий n = 2 и m = 3а) Докажите, что граф на рис. 10.3 не имеет гамильтонова цикла. Указание.Нужно рассмотреть ситуацию, когда гипотетический гамильтонов цикл проходит через центральный узел. Откуда он может исходить и куда он можетвести, не отсекая при этом части графа от гамильтонова цикла?б) Для каких значений n и m гамильтонов цикл существует?10.1.5.
(!) Предположим, что у нас есть способ кодировки контекстно-свободныхграмматик с помощью некоторого конечного алфавита. Рассмотрим следующие два языка.1.L1 = {(G, A, B) | G — (закодированная) КС-грамматика, A и B — (закодированные) переменные G, причем множества терминальных цепочек, выводимых из A и B, совпадают}.10.1. ÊËÀÑÑÛ P È NPСтр. 4354352.L2 = {(G1, G2) | G1 и G2 — (закодированные) КС-грамматики, и L(G1) = L(G2)}.Выполните следующие задания:а) (∗) покажите, что L1 полиномиально сводится к L2;б) покажите, что L2 полиномиально сводится к L1;в) (∗) что можно сказать об NP-полноте L1 и L2 на основании а и б?10.1.6. P и NP, как классы языков, обладают определенными свойствами замкнутости.Покажите, что класс P замкнут относительно следующих операций:а) обращение;б) (∗) объединение;в) (∗!) конкатенация;г) (!) замыкание (звездочка);д) обратный гомоморфизм;е) (∗) дополнение.10.1.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
