Алгоритмы - построение и анализ (1021735), страница 228
Текст из файла (страница 228)
Если же алгоритм делает полиномиальное число вызовов такой процедуры, то общее время работы может быть экспоненциальным. 34.1-6. Покажите, что класс Р, который рассматривается как множество языков, замкнут относительно операций объединения, пересечения, конкатенации, дополнения и замыкания Клини. Другими словами, если Ьы Ьз Е Р, то Ь1 0 Ьз е Р и т.д.
34.2 Проверка за полиномиальное время Теперь рассмотрим алгоритм, "проверяющий" принадлежность языку. Например, предположим, что в данном экземпляре (С, и, о, Й) задачи принятия решения РАТН задан также путь р из вершины и в вершину щ Легко проверить, превышает ли длина пути р величину к. Если она не превышает эту величину, путь Глава 34. МР-полнота 1101 р можно рассматривать как "сертификат" того, что данный экземпляр действительно принадлежит РАтн.
Для задачи принятия решения Рлтн такой сертификат, по-видимому, не дает ощутимых преимуществ. В конце концов, эта задача принадлежит классу Р (фактически ее можно решить за линейное время), поэтому проверка принадлежности с помощью такого сертификата занимает столько же времени, сколько и решение задачи. А теперь исследуем задачу, для которой пока неизвестен алгоритм принятия решения с полиномиальным временем работы, но если имеется сертификат, то легко выполнить его проверку.
Гамильтоиовы циклы Задача поиска гамильтоновых циклов в неориентированном графе изучается уже более ста лет. Формально гамилътоигв цикл (папп1гоп1ап сус1е) неориентированного графа С = (У, Е) — это простой цикл, содержащий все вершины множества К Граф, содержащий гамильтонов цикл, называют гамильтоновым (Ьашй1оп1ап); в противном случае он является ивгвмильтоиовым (попЬашй1ошап). В книге Бонди (Вопс$у) и Мьюрти (МпгГу) 145) цитируется письмо Гамильтона (ЖК.
Наппйоп) с описанием математической игры на додекаэдре (рис. 34.2а), в которой один игрок отмечает пятью булавками пять произвольных последовательных вершин, а другой игрок должен дополнить этот путь, чтобы в результате получился путь, содержащий все вершины. Додекаэдр является гамильтоновым графом, и один из гамильтоновых циклов показан на рис.
34.2а. Однако не все графы являются гамильтоновыми. Например, на рис. 34.2б показан двудольный граф ',л Рис. 34.2. Примеры гамильтонового (а) и негамильтонового (б) графов Часть ч11. Избранные темы 1102 с нечетным количеством вершин. В упражнении 34.2-2 предлагается доказать, что все такие графы негамильтоновы. Задачу о гамильтоновых циклах (лаш111ошап-сус1е ргоЫеш), в юторой нужно определить, содержит ли граф С гамильтонов цикл, можно определить как форма ьиый язык: НАм Сусли = ((С): С вЂ” гамильтонов граф) . Как алгоритм мог бы распознать язык НАм Сус1.в? Для заданного экземпляра задачи (С) можно предложить алгоритм принятия решения, который бы формировал список всех перестановок вершин графа С, а затем проверял бы каждую перестановку, не является ли она гамильтоновым путем.
Чему равнялось бы время работы такого алгоритма? При использовании "рационального" юдирования графа с использованием матриц смежности количество вершин т графа равно й (~/й), где п = !(С) ! — длина юда для графа С, Всего имеется т! возможных перестановок вершин, поэтому время работы алгоритма равно й (т!) = й (~/й1) = й (2~к), и оно не ведет себя в асимптотическом пределе как О (и") ни для какой юнстанты к. Таким образом, время работы подобного прямолинейного алгоритма не выражается полиномиальной функцией.
Фактически, как будет доказано в разделе 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
