Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 228
Текст из файла (страница 228)
Фактически, как будет доказано в разделе 34.5, задача о гамильтоновых циклах является ХР-полной. Алгоритмы верификации Рассмотрим несюлько упрощенную задачу. Предположим, что приятель сообщил вам, что данный граф С вЂ” гамильтонов, а затем предложил доказать зто, предоставив последовательность вершин, образующих гамильтонов цикл. Очевидно, в такой ситуации доказательство было бы достаточно простым: следует просто проверить, что предоставленный цикл является гамильтоновым, убедившись, что данная последовательность вершин является перестановкой множества всех вершин У и что каждое встречающееся в цикле ребро действительно принадлежит графу. Легко понять, что подобный алгоритм верификации можно реализовать так, чтобы время его работы было равно О (пз), где п — длина графа С в закодированном виде.
Таким образом, доказательство того, что гамильтонов цикл в графе существует, можно проверить в течение полиномиального времени. Определим алгоритм верификации (чепйсабоп а1коп1)лп) как алгоритм А с двумя аргументами, один из которых является обычной входной строкой х, а второй — бинарной строкой у под названием сертификат (сегбйсазе). Двухаргументный алгоритм А верифицирует (чепбез) входную строку х, если существует сертификат у, удовлетворяющий уравнению А (х, у) = 1. Язык, проверенный алгоритмом верификации А, — это множество Ь = (х Е (О, 1)': существует у Е (О, 1)* такой, что А (х, у) = 1) .
Глава 34. МР-полнота 1103 Интуитивно понятно, что алгоритм А верифицирует язык Ь, если для любой строки х б Ь существует сертификат у, позволяющий доказать с помощью алгоритма А, что х Е Ь. Кроме того, для любой строки х ф Ь не должно существовать сертификата, доказывающего, что х Е Ь. Например, в задаче о гамильтоновом цикле сертификатом является список вершин некоторого гамильтонового цикла. Если граф гамильтонов, то гамильтонов цикл сам по себе предоставляет достаточно информации для верификации этого факта.
В обратном случае, т.е. если граф не является гамильтоновым, то не существует списка вершин, позволяюшего обмануть алгоритм верификации и установить, что граф является гамильтоновым, так как алгоритм верификации производит тщательную проверку предложенного "цикла", чтобы убедиться в его правильности. КЛаСС СЛОЖНОСТИ [ч[Р ясяасс елоогсггосиаи ХР (сошр!ехйу с[вяз ХР) — это класс языков, которые можно верифнцировать с помощью алгоритма с полиномиальным временем работыб. Точнее говоря, язык принадлежит классу ХР тогда и только тогда, когда существует алгоритм А с двумя входными параметрами и полиномиальным временем работы, а также константа с, такая что Ь = (х е (О, 1)': существует сертификат у ([у~ = О ([х[')) такой, что А(х,у) = Ц. При этом говорят, что алгоритм А веригрииируеиг (чепГу) язык Ь за иолииомиальиое время (ш ро1упоппа! Йпе).
Из проводимого ранее обсуждения задачи о гамильтоновых циклах следует, что задача Нлм Сусье е ХР (всегда приятно знать, что некоторое важное множество — не пустое). Кроме того, если я е Р, то Ь Е ХР, поскольку при наличии алгоритма с полиномиальным временем работы, способного распознать язык Ь, алгоритм легко преобразовать в алгоритм верификации с двумя аргументами, который просто игнорирует сертификат и принимает именно те входные строки, для которых он устанавливает принадлежность языку Ь. Таким образом, Р С ХР.
Не известно, выполняется лн равенство Р = ХР, но, по мнению большинства исследователей, классы Р и ХР— не одно и то же. Интуитивно понятно, что класс Р состоит из задач, которые решаются быстро. Класс же ХР состоит из задач, решение которых можно быстро проверить. Возможно, из опыта вы уже знаете, что Название "ХР" обозначает "попоесепп!п)зс)с ро[упоппа1 бше" [нелетерминистическое полиномиальное время).
Класс ХР изначально изучался в контексте нелетерминизма, но нами используется более простое, хотя и эквивалентное понятие верификации. В книге Хопкрофта [Хорсте[С) и Ульмана [О11гпап) [156! хорошо изложено понятие ХР-полноты в терминах нелетерминистических вычислительных моделей. Часть Ч11. Избранные темы 1104 ' Р- иг=жьнг чв:=со-%' '-';.:фаз~~ / и Рис. 34.3.
Четыре возможных вида отношений между классами слож- ности часто сложнее решить задачу с самого начала, чем проверить представленное решение, особенно если вы ограничены во времени. Среди ученых, занимающихся теорией вычислительных систем, общепринято считать, что эта аналогия распространяется на классы Р и ХР и, следовательно, что класс ХР содержит языки, не принадлежащие классу Р. Существует более веское свидетельство того, что Р ~ ХР, — наличие языюв„ являющихся "ХР-полными". Класс этих задач исследуется в разделе 34.3.
Помимо вопроса о соблюдении соотношения Р ~ ХР, остаются нерешенными многие другие фундаментальные вопросы. Несмотря на интенсивные исследования в этой области, никому не удалось установить, замкнут ли класс ХР относительно операции дополнения. Другими словами, следует ли из соотношения Л Е ХР соотношение Ь Е ХР? Можно определить класс сложности со-ХР (сошр!ехйу с!ааа со-ХР) как множество языюв Ь, для которых выполняется соотношение А Е ХР.
Вопрос о том, замкнут ли класс ХР относительно дополнения, можно перефразировать как вопрос о соблюдении равенства ХР = со-ХР. Поскольку класс Р замкнут относительно дополнения (упражнение 34.1-6), отсюда следует, что Р С ХР Псо-ХР. Однако, опять же не известно, выполняется ли равенство Р = ХР П со-ХР, т.е. существует ли хоть один язык в множестве ХР П со-ХР— Р. На рис. 34.3 представлены четыре возможные ситуации. На каждой диаграмме одна область, содержащая другую, указывает, что внутренняя область является собственным подмножеством внешней.
В части а рисунка показана ситуация, соответствующая равенству Р = ХР = со-ХР. Большинство исследователей считает этот сценарий наименее вероятным. В части б показано, что если класс ХР замкнут относительно дополнения, то ХР = со-ХР, но не обязательно справедливо равенство Р = ХР.
В части в изображена ситуация, когда Р = ХРПсо-ХР, но Глава 34. ХР-полнота 1105 Упражнения 34.2-1. Рассмотрим язык Оимн 1зомокрным = ((Сы Сз): Сз и Сз — изоморфные графы) . Докажите, что Оилрн 1зОмОКРн!зм е ХР, описав алгоритм с полиноми- альным временем работы, позволяющий верифицировать этот язык. Докажите, что если С вЂ” неориентированный двудольный граф с нечет- ным количеством вершин, то он не является гамильтоновым. 34.2-2. 34.2-3. Покажите, что если НАМ С~'с~.в Е Р, то задача о выводе списка вершин гамильтонового цикла в порядке их обхода разрешима в течение полиномиального времени. 34.2-4.
Докажите, что класс языков ХР замкнут относительно операций объединения, пересечения, конкатенации и замыкания Клини. Обсудите замкнутость класса ХР относительно дополнения. 34.2-5. Покажите, что любой язык из класса ХР можно распознать с помощью алгоритма, время работы которого равно 2О(" ), где )с — некоторая константа. 34.2-6.
Гамильтонов луюпь (лапн11ошал рай) графа — это простой путь, который проходит через каждую вершину ровно по одному разу. Покажите, что язык НАМ РАтн = ((С, и, о): в графе С имеется гамильтонов путь от и к о) принадлежит классу ХР. 34.2-7. Покажите, что задачу о гамильтоновом пути в ориентированном ациклическом графе можно решить в течение полиномиального времени. Сформулируйте эффективный алгоритм решения этой задачи. 34.2-8. Пусть ф — булева формула, составленная из булевых входных переменных хы хз,..., хы операторов НЕ (.
), И (Л), ИЛИ (~/) и скобок. Формула класс ХР не замкнут относительно дополнения. И наконец, в части г выполняются соотношения ХР ф со-ХР и Р ф ХР со-ХР. Большинство исследователей считают эту ситуацию наиболее вероятной. Таким образом, к сожалению, наше понимание того, какие именно взаимоотношения существуют между классами Р и ХР, далеко не полные.
Тем не менее, в процессе изучения теории ХР-полноты станет понятно, что с практической точки зрения недостатки доказательства трудноразрешимости задачи не играют такой важной роли, как можно было бы ожидать. Часть Ч1!. Избранные темы 1106 ф называется тавиюлогией (1ацю1ояу), если для всех возможных наборов входных переменных в результате вычисления формулы получается значение 1.
Определите язык булевых формул ТАотоюоу, состоящий из тавтологий. Покажите, что ТАотоьооу Е со-ХР. 34.2-9. Докажите, что Р С со-ХР. 34.2-10. Докажите, что если ХР зЬ со-ХР, то Р зЬ ХР. 34.2-11. Пусть С вЂ” связный неориентированный граф, содержащий не менее трех вершин, а Ф вЂ” граф, полученный путем соединения всех пар вершин, которые связаны в графе С путем, длина которого не превышает 3 ребер. Докажите, что граф Сз гамильтонов. (Указание: постройте остовиое дерево графа 6 и воспользуйтесь индукцией.) 34.3 ХР-полнота и приводимость По-видимому, одна из веских причин, по которым специалисты в области теории вычислительных систем полагают, что Р ф ХР, — наличие класса "ХР- полных" задач.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
