Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 99
Текст из файла (страница 99)
1. Е принадлежит ЛГР. 2. Для всякого языка Е'из ЛР существует полиномиальное сведение Е' к Е. ГЛАВА 10. 'ГРУДНОРЕШАЕМЬЕЕ ПРОБЛЕМЫ 432 Как мы увидим, примером ХР-полной проблемы является проблема коммивояжера (см. раздел 10.1.4). Предполагается, что Р ~ МР, и, в частности, что все ХР-полные проблемы содержатся в ЛР- Р, поэтому доказательство ХР-полноты проблемы можно рассматривать как свидетельство того, что она не принадлежит Р. Вначале докажем ХР-полноту так называемой проблемы выполнимости булевой формулы (ВЫП), показав, что язык всякой НМТ с полиномиальным временем полиномиально сводится к ВЫП.
Имея в распоряжении некоторые ХР-полные проблемы, можно доказать ХР-полноту еще одной, новой проблемы посредством полиномиального сведения к ней одной из известных проблем. Следующая теорема объясняет, почему такое сведение доказывает, что новая проблема является Хр-полной. Теорема 10.4. Если проблема Р, является ХР-полной, и существует полиномиальное сведение Р~ к Рь то проблема Рз также Хр-полна. Доказательство.
Нужно показать, что всякий язык ь из ЛТ полиномиально сводится к Р,. Мы знаем, что существует полиномиальное сведение 1. к Рй это сведение занимает некоторое полиномиапьное время р(а). Поэтому цепочка и из ь' длиной и преобразуется в цепочку х из Ро длина которой не превосходит р(п). Мы также знаем, что существует полиномиальное сведение Р, к Рй пусть это сведение занимает полнномиальное время п(т). Тогда зто сведение преобразует х в некоторую цепочку у из Рь за время, не превосходящее о()з(п)).
Таким образом, преобразование и в у занимает времени не более р(п) + о(р(п)), которое является полиномиальным. Следовательно, 1 полиномиально сводим к Р,. Поскольку 1 — произвольный язык из ЛР, то мы показали, что все проблемы класса Л)э полиномиально сводятся к Рь т.е. Рз является ХР-полной. П Тчр-трудные проблемы Некоторые проблемы Т, трудны настолько, что, хотя и можно доказать, что для них выполняется условие 2 из определения ХР-полноты (всякий язык из ЛР сводится к 1 за полиномиальное время), условие 1 — что 1, принадлежит ЛР— мы доказать не можем. Если это так, то Т, называется ХР-трудной. До сих пор в отношении проблем, требующих для решения экспоненциального времени, использовался нестрогий термин "труднорешаемая".
Вообще говоря, термин "труднорешаемая" в значении "ХР-трудная" использовать можно, хотя могут существовать проблемы, требующие экспоненциального времени, несмотря на то, что в строгом смысле они не являются ХР-трудными. Для доказательства ХР-трудности проблемы 1 достаточно показать высокую вероятность того, что Т. требует экспоненциального или большего времени. Однако если 1. не принадлежит классу Л')э, то ее очевидная трудность никак не может служить подтверждением того, что все ХР-полные проблемы трудны, т.е.
может выясниться, что Р = ЛlР, но при этом 1, все равно требует экспоненциального времени. 433 10.1. КЛАССЫ Р И ХР Есть еще одна, более важная, теорема, которую нужно доказать для ХР-полных проблем: если любая из них принадлежит Р, то весь класс А!Р содержится в Р. Но мы твердо верим, что в МР содержится много проблем, не принаалежаигих Р. Таким образом, доказательство ХР-полноты проблемы мы считаем равносильным доказательству того, что у нее нет алгоритма решения с полиномиальным временем, и позтому она не имеет хо- рошего компьютерного решения. Теорема 10.5.
Если некоторая ХР-полная проблема Р принадлежит Р, то Р = МР. Доказательство. Предположим, что Р одновременно и ХР-полна, и принадлежит Р. Тогда любой язык А из ЛР полиномиально сводится к Р. Если Р принадлежит Р, то и 2. принадлежит 'Р (см. Раздел 10.1.5). П 10.1.7. Чпражнения к разделу 10.1 10.1.1. Каким будет ОДМВ для графа на рис 10.1, если вес его ребер изменить следующим образом: а) (э) вес 1О ребра (1, 3) изменить на 25; б) изменить вес ребра (2, 4) на 16. Альтернативные определения ХР-полноты Конечной целью изучения ХР-полноты является теорема!0.5, т.е. поиск проблем Р, принадлежность которых классу Р влечет равенство Р=А!Р. Определение "ХР- полноты", использованное здесь, часто называется полнотой по Карпу, поскольку оно впервые было использовано Р.
Карпом в фундаментальной работе на данную тему. Этому определению соответствует любая проблема, предположительно удовлетворяющая условиям теоремы ! 0.5. Однако существуют другие, более широкие понятия Хр-полноты, для которых теорема 10.5 также справедлива. Например, С Кук в своей первой работе, посвященной данному предмету, дал следующее определение "ХР-полноты" проблемы Р. Проблему Р он назвал ХР-полной, если, имея для проблемы Р оракул — механизм, который за единицу времени определяет, принадлежит ли данная цепочка Р, — можно распознать всякий язык из А1Р за полиномиальное время.
Этот тип ХР-полноты называют полнотой па Куку. В некотором смысле, полнота по Карпу есть частный случай атой полноты, когда оракулу задается лишь один вопрос. Однако полнота по Куку допускает отрицание ответа. Можно, например, задать оракулу некоторый вопрос, а в качестве ответа взять противоположное тому, что он ответит. Согласно определению полноты по Куку, дополнение ХР-полной проблемы также является ХР-полной проблемой. Используя же более узкое определение полноты по Карпу, можно указать важное отличие ХР-полных проблем от их дополнений. Это делается в разделе 11. 1. 434 ГЛАВА 10.
ТРуднОРешАемые пРОБлемы 10.1.2. Каким будет гамильтонов цикл минимального веса для графа на рис. 10.1, если в него добавить ребро с весом 19, соединяюшее узлы 1 и 4? 10.1.3. (в!) Предположим, что существует )чр-полная проблема с детерминированным решением, занимающим время 0(вь" "). Заметим, что эта функция лежит меж- ду полнномами и экспонентами и не принадлежит ни одному из этих классов функций. Что можно сказать о времени, необходимом для решения произвольной проблемы из Ас?з? 10.1.4. (1!) Рассмотрим графы, узлами которых являются узлы целочисленной решетки в и-мерном кубе со стороной длины т, т.е, векторы (!о !ь ..., 1„), где каждое ~, находится в диапазоне от 1 до и (или от 0 до т — 1). Ребро между двумя узлами существует тогда и только тогда, когда они различаются на единицу ровно по одной координате.
Например, вариант и = 2 и и = 2 представляет собой квадрат, л = 3 и т = 2 — куб, а и = 2 и т = 3 — граф, изображенный на рис. ! 0.3. Некоторые из этих графов имеют гамильтонов цикл, некоторые — нет. Например, квадрат имеет такой цикл. Куб — тоже, хотя это и не очевидно; примером является цикл (О, О, 0),(0, О, 1), (О, 1, 1), (О, 1, 0),(1, 1, 0), (1, 1, 1), (1, О, 1), (1, О, 0) и снова (О, О, 0).
Граф на рис. 10.3 гамильтонова цикла не имеет. Рис. Д13 Граф, соответствующий п — — 2 и т = 3 а) Докажите, что граф на рис. 10.3 не имеет гамильтонова цикла. Указание. Нужно рассмотреть ситуацию, когда гипотетический гамильтонов цикл проходит через центральный узел. Откуда он может исходить и куда он может вести, не отсекая при этом части графа от гамильтонова цикла? б) Для каких значений п и т гамильтонов цикл существует? 10.1.5. (!) Предположим, что у нас есть способ кодировки контекстно-свободных грамматик с помощью некоторого конечного алфавита.
Рассмотрим следуюшие два языка. 1. Е, = ((б, А, В) ~ Π— (закодированная) КС-грамматика, А и  — (закодированные) переменные б„причем множества терминальных цепочек, выводимых из А и В, совпадают). 435 10.1. КЛАССЫ Р И !ЧР 2. Ез =- ((Сь бз) ~ С~ и 6~ — (закодированные) КС-грамматики, и Е(Ор) = Е(Оз)). Выполните следующие задания: а) (*) покажите, что Е, полиномиально сводится к Е; б) покажите, что Ез полиномиально сводится к Е,; в) (е) что можно сказать об МР-полноте Е, и Е на основании а и б? 10.1.6. Р и Л'Р, как классы языков, обладают определенными свойствами замкнутости. Покажите, что класс 'Р замкнут относительно следующих операций: а) обращение; б) (в) объединение; в) (в1) конкатенация; г) (!) замыкание (звездочка); д) обратный гомоморфизм; е) (в) дополнение. 10.1.7.
Класс ЛГР также замкнут относительно каждой из операций, перечисленных в упражнении 10.1.6, за (предполагаемым) исключением операции дополнения (пункт е). Замкну~ ли класс ЛЕР относительно дополнения — неизвестно; этот вопрос обсуждается в разделе 11.1. Докажите, что МР замкнут относительно операций из пунктов а — д упражнения 10.1.6. 10.2. Первая 1ч)Р-полная проблема Теперь познакомимся с первой МР-полной проблемой — проблемой выполнимости булевых формул. Ее ХР-полнота доказывается путем непосредственного сведения к ней языка любой недетерминированной )Ь(Т с полиномиальным временем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
