Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 247
Текст из файла (страница 247)
Фактически Р является также классом языков, которые могут быть приняты за полиномиальное время. Теорема 34.3 Р = (Ь: ь принимается алгоритмом с полиномиапьным временем работы) аннтересуюшнйса читатель найдет лополннтельную информацию а сомье Хартманиса (Напюмна) и стирнса сзтеагпа) (161). Глава ЗК //Р-аалвата //09 Двказашельсшва. Поскольку класс языков, которые распознаются алгоритмами с полиномиальным временем работы, представляет собой подмножество класса языков, которые принимаются алгоритмами с полиномиальным временем работы, остается лишь показать, что если язык Л принимается алгоритмом с полиномиальным временем работы, то он также распознается алгоритмом с полиномиальным временем работы.
Пусть Ь вЂ” язык, который принимается некоторым алгоритмом с полиномиальным временем работы А. Воспользуемся классическим "модельным" доказательством, чтобы сконструировать другой алгоритм с полиномиальным временем работы А', который бы распознавал язык Ь. Поскольку алгоритм А принимает язык Ь за время 0(пь), где /в — некоторая константа, существует такая константа с, что алгоритм А принимает язык Ь не более чем за сп" шагов. Для любой входной строки х алгоритм А' моделирует спь шагов алгоритма А.
После этого алгоритм А' проверяет поведение алгоритма А. Если он принял строку х, то алгоритм А' также принимает эту строку, выводя значение 1. Если же алгоритм А не принял строку х, то алгоритм А' отвергает эту строку, выводя значение О. Накладные расходы алгоритма А', моделирующего алгоритм А, приводят к увеличению времени работы не более чем на полиномиальный множитель, поэтому А' — алгоритм с полиномиальным временем работы, распознающий язык Л. Заметим, что доказательство теоремы 34.2 является неконструктивным.
Для данного языка Ь е Р граница времени работы алгоритма А, который принимает язык Ь, на самом деле может быть неизвестна. Тем не менее известно, что такая граница существует, поэтому существует алгоритм А', способный проверить эту границу, даже если его не всегда удается легко найти. Упражнения 34.1.1 Определим задачу оптимизации ЬОХСЕБТ-РАТН-ЬЕХСТН как отношение, связывающее каждый экземпляр задачи, состоящий из неориентированного графа и двух его вершин, с количеством ребер в самом длинном простом пути между этими двумя вершинами. Определим задачу принятия решения ЬОХСЕЯТ-РАТН = ((С, и, о, /в): С = (К,Е) — неориентированный граф, и,в/ Е К, /в ) Π— целое число, и существует простой путь из и в о в С, состоящий как минимум из /в ребер). Покажите, что задачу оптимизации 1 ОМСЕБТ-РАТН-ЬЕМСТН можно решить за полиномиальное время тогда и только тогда, когда ЬОХСЕЯТ-РАТН-ЬЕХСТН е Р.
34.1.2 Дайте формальное определение задачи поиска самого длинного простого цикла в неориентированном графе. Сформулируйте соответствующую задачу принятия решения. Опишите язык„соответствующий этой задаче принятия решения. пго Часть И1. Иэбранные темы 34.1.3 Разработайте формальное кодирование ориентированного графа в виде бинарных строк лля представления с помощью матриц смежности. Выполните то же самое для представления с использованием списка смежных вершин.
Докажите, что этн два представления полиномиально связаны. 34.1.4 Является ли алгоритм динамического программирования для решения дискретной задачи о рюкзаке, который предлагалось разработать в упр. 16.2.2, алгоритмом с полииомиальным временем работы? Обоснуйте свой ответ.
34.1.5 Покажите, что алгоритм, который содержит не больше некоторого постоянного количества вызовов процедуры с полиномиальным временем работы, сам работает полиномиальное время. Если же алгоритм делает полиномиальное число вызовов такой процедуры, то общее время работы может быть экспоненциальным. 34.1.6 Покажите, что класс Р, юторый рассматривается как множество языюв, за- мкнут относительно операций объединения, пересечения, конкатенации, допол- нения и замыкания Клини. Другими словами, если Ьь 1,з Е Р, то 1,1 0 Ьз е Р, Ь| й 1г с Р, 111з с Р, 11 Е Р и 11 б Р, 34.2. Проверка за нолнномнальное время Теперь рассмотрим алгоритм, проверяющий принадлежность языку.
Например, предположим, что в данном экземпляре (С, и, о, )с) задачи принятия решения РАТН задан также путь р из вершины и в вершину ю. Легко проверить, превышает ли длина пути р величину эс. Если она не превышает эту величину, путь р можно рассматривать как "сертификат" того, что данный экземпляр действительно принадлежит РАТН. Для задачи принятия решения РАТН такой сертификат, по-видимому, не дает ощутимых преимуществ.
В юнце концов, эта задача принадлежит классу Р (факгически ее можно решить за линейное время), поэтому проверка принадлежности с помощью такого сертификата занимает столько же времени, сколько и решение задачи. А теперь исследуем задачу, для которой пока неизвестен алгоритм принятия решения с полиномиальным временем работы, но если имеется сертификат, то выполнить его проверку очень легко. Гамильтоновы циклы Задача поиска гамильтоновых циклов в неориентированном графе изучается уже более ста лет. Формально гамильтонов цикл (папи!юп(ап сус!е) неориентированного графа С = (г, Е) представляет собой простой цикл, содержащий все вершины множества Ъ'. Граф, содержащий гамильтонов цикл, называют гв- Глава 54, 7(Р-полнота г (а) (б) Рмс.
36.2. (а) Граф, представпяюший вершины, ребра н грани додекаэдра; штриховкой показан один нз его гамильтоновых циклов. (6) Двудольный граф с нечетным количеством вершин. Все такие графы негамнльтоновы. мильиюноиым ([)апп[(ошап); в противном случае он является негамильтоноеьвм (поп))аш[[Юп[ап). Он назван так в честь УР. Гамильтона (%.Гх. Ншп[1(оп), шпорый описал математическую игру на додеказлре (рис. 34.2,(а)), в которой один игрок отмечает пятью булавками пять произвольных последовательных вершин, а другой игрок должен так дополнить зтот путь, чтобы в результате получился путь, содержащий все вершиныу. Додекаэдр является гамильтоновым графом, и один из гамильтоновых циклов показан на рис. 34.2, (а).
Однако не все графы являются гамильтоновыми. Например, на рис. 34.2,(б) показан двудольный граф с нечетным количеством вершин. В упр. 34.2.2 предлагается доказать, что все такие графы негамильтоновы. Задачу о гамильигоноеых циклах (Ьап)1(оп[ел-сус1е ргоЫеп)), в которой нужно выяснить, содержит ли (раф С гамильтонов цикл, можно определить как формальный язык: НАМ-СУС1 Е = ((С): С является гамильтоновым графом) Как алгоритм мог бы распознать язык НАМ-СУСЛЕ? Для заданного экземпляра задачи (С) можно предложить алп)ритм принятия решения, который сначала формировал бы список всех перестановок вершин графа С, а затем проверял каждую перестановку, — не является ли она гамильтоновым путем? Чему рав- тв письме ст 17 огаября 1856 пжа своему другу Джону Грейвзу ()ойп Т.
Отачпп Гамильтон пишет [156, р. 624): "Л обнаружил, что кекогсрьж молодых людей весьма позабавила новая математнческаа игра, в мисрой одп» человек ставит пать кнопок в любые пять последовательных тачек ... а другой юрок затем пытвстсх всювить остальные пхтиадоать кнопок (что согласно теории, изложенной в данном письме, всегда возможно) так. чтобы получился пикл, так.
чтобы были охвачены все тачки, и чтобы он заюичнлся рядом с точюй, с которой начал Шютивиикт 22/2 Часть Г11 Иэбранные темы нялось бы время работы такого алгоритма? Прн использовании "рационального" кодирования графа с использованием матриц смежности количество вершин гп графа равно й(э/и), где и = ~(С) ~ — длина кода графа С. Всего имеется гп! возможных перестановок вершин, поэтому время работы алгоритма равно й(пз() = й(~/и!) = й(2нсб), и оно не ведет себя в асимптотическом пределе как 0(п") ни для какой константы lс. Таким образом, время работы подобного прямолинейного алгоритма не выражается полиномиальной функцией. Фактически, как будет доказано в разделе 34.5, задача о гамильтоновых циклах является ХР-полной.
Алгоритмы верификации Рассмотрим несколько упрощенную задачу. Предположим, что приятель сообщил вам, что данный граф С вЂ” гамильтонов, а затем предложил доказать это, предоставив последовательность вершин, образующих гамильтонов цикл. Очевидно, в таюй ситуации доказательство было бы достаточно простым: следует просто проверить, является ли предоставленный цикл гамильтоновым, убедившись, что данная последовательность вершин является перестановкой множества всех вершин 1' н что каждое встречающееся в цикле ребро действительно принадлежит графу. Легко понять, что подобный алгоритм верификации можно реализовать так, чтобы время его работы было равно 0(пз), где п — длина графа С в закодированном виде.
Таким образом, доказательство того, что гамильтонов цикл в графе существует, можно проверить за полиномиальное время. Определим алгоритм верификации (чепбсабоп а(яопбнп) как алгоритм А с двумя аргументами, один из которых является обычной входной строкой х, а второй — бинарной строюй у под названием сертификааэ (сегбйса1е).
Двух- аргументный алгоритм А верифицирует (чепйез) входную строку х, если сущеегвует сертификат у, такой, что А(х, у) = 1. Язык, верифицироваииый алгоритмом верификации А, представляет собой множество Ь = (х Е (О, 1)': существует у Е (О, 1)', такое, что А(х, у) = 1) Интуитивно понятно, что алгоритм А верифицирует язык Ь, если для любой строки х е Т, существует сертификат у, позволяющий доказать с помощью алгоритма А, что х е Ь. Кроме того, для любой строки х ф Т, не должно существовать сертификата, доказывающего, что х е Т,.
Например, в задаче о гамнльтоновом цикле сертификатом является список вершин некоторого гамильтонового цикла. Если граф гамильтонов, то гамильтонов цикл сам по себе предоставляет достаточно информации для верификации этого факта. В обратном случае, т.е. если граф не является гамильтоновым, не существует списка вершин, позволяющего обмануть алгоритм верификации и установить„что граф является гамильтоновым„ так как алгоритм верификации выполняет тщательную проверку предложенного "цикла", чтобы убедиться в его правильности. Глава 34.
)УР-палноша Класс сложиости ХР Клесс сложности ХР (сошр[ехйу с1азз ХР) — это класс языков, которые можио верифицировать с помощью алгоритма с полииомиальиым временем работый. Точнее говоря, язык Т, принадлежит классу ХР тогда и только тогда, когда существуют алгоритм А с двумя входными параметрами и полииомиапьиым временем работы, а также константа с, такая, что Ь = (х Е (О, 1)*: существует сертификат у с [у) = 0([х['), такой, что А(х, у) = 1) . При этом говорят, что алгоритм А верифииирует язык Т. за налиномивлъное время.
Из проведенного ранее обсуждения задачи о гамильтоиовых циклах следует, что задача НАМ-С'т'СЕЕ е ХР (всегда приятно знать, что некоторое важное множество — ие пустое). Кроме того, если Ь е Р, то Ь е ХР, поскольку при наличии алгоритма с полииомиапьиым времеием работы, способного распознать язык А, алгоритм легко преобразовать в алгоритм верификации с двумя аргументами, который просто игнорирует сертификат и принимает именно те входные строки, для которых ои устанавливает принадлежность языку Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
