Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 248
Текст из файла (страница 248)
Таким образом, Р С ХР. Неизвестно, выполняется ли равенство Р = ХР, но, по мнению большинства исследователей, классы Р и ХР— ие одно и то же. Интуитивно понятно, что класс Р состоит из задач, которые решаются быстро. Класс же ХР состоит из задач, решеиие которых можно быстро проверить. Возможно, из своего опыта вы уже знаете, что часто сложнее решить задачу с самого начала, чем проверить представленное решение, особенно если вы ограничены во времени. Среди ученых, занимающихся теорией вычислительных систем, распространено мнение, что эта аналогия распространяется и иа классы Р и ХР, а следовательно, что класс ХР содержит языки, ие принадлежащие классу Р.
Существует более веское, хотя и ие окончательное, свидетельство того, что Р ~ ХР, — наличие языков, являющихся "ХР-полиыми". Класс этих задач рассматривается в разделе 34.3. Помимо вопроса о выполнении соотношения Р ф ХР, остаются иерешеииыми и многие другие фундаментальные вопросы. На рис. 34.3 показаны некоторые возможные сценарии. Несмотря иа интенсивные исследования в этой области, никому ие удалось установить, замкнут ли класс ХР относительно операции дополнения. Другими словами, следует ли из соотношения Ь е ХР соотношение Х е ХР? Можно определить класс сложности со-ХР (сошр!ехйу с!азв со-ХР) как множество языков Е,, таких, что Х е ХР. Вопрос о том, замкнут ли класс ХР относительно дополнения, можно перефразировать как вопрос о выполиеиии равенства ХР = со-ХР.
Поскольку класс Р замкнут отиосительио допол- Япазванне "МР" означает "попаезеппшмйс ро)упоппа( йше" (нелетермнннстнческое полнномнальное время). Класс МР нзнячально изучался в контексте нелетермнннзма, но нами нспользуется более простое, ютя н зканвалштлое ванятке всрнфнквпнн. В тате Хопкрофта (Морской) н Ульмана (П(йпап) [) 791 кореше нзло. мено понятие МР-полноты в термннак нелетермнннстнчсскнк вычнслнтельныл молелеа Ш4 Часть )Тй Избранные темы Фл,:1((Р:,ма((((()вз, (в) (6) (г) (в) рис.
34З. Четыре возможных вида отношении между классамн сложности. На представаенной диаграмме полное включение одной области в другую указывает на отношение истинного подмножества. (а) Р = ХР = со-ХР. Большинство исследователей полагают, что эта возможность наименее прашоподобна. (6) Если ХР замкнут относительно дополнения, та ХР = со.ХР, но при этом не обязательно выполняется соотношение Р = ХР. (в) Р = ХР Г) со.ХР, но ХР не замкнут относигельно дополнения, (г) ХР )( со-ХР и Р ~ ХР Г) со.ХР. Большинство исследователей полагают эту возмткность наиболее правдоподобной. нения (упр. 34.1.6), из упр. 34.2.9 следует, что Р С 1((Р П со-)ЧР. Однако, опять же, неизвестно, выполняется ли равенство Р = ХР П со-)ЧР, или в множестве ХР П со-ХР— Р существует ли хотя бы один язык.
Таким образом, к сожалению, наше понимание того, какие именно взаимоотношения существуют между классами Р и (ЧР, далеко не полное. Тем не менее, несмотря на то что мы неспособны доказать сложность конкретной задачи, доказав ее (ЧР-полноту, можно получить о ней очень важную информацию. Упражнении 34.2.1 Рассмотрим язык СВАРН-1БОМОВРН1БМ = ((С(,СЗ): С( н Сз являются изоморфными графами). Докажите, что СВАРН-1БОМОВРН1БМ с )ЧР, описав алгоритм с полиномиальным временем работы, позволюощий верифицировать этот язык.
34.2.2 Докажите, что если С вЂ” неориентированный двудольный граф с нечетным каличеством вершин, то он не является гамильтоновым. 34.2.3 Покажите, что если НАМ-СУС1 Е е Р, то задача о выводе списка вершин гамильтонового цикла в порядке их обхода разрешима в течение полиномиального времени. !!!5 Глава 54 5гР-волиовва 34.2.4 Докажите, что класс языков ХР замкнут относительно операций объединения, пересечения, конкатенации и замыкания Клини. Обсудите замкнутость класса ХР относительно дополнения. 34.2.3 Покажите, что любой язык из класса ХР можно распознать с помощью алгоритма, время работы которого равно 2Н(" ), где /с — некоторая константа. 34.2.6 Гииилыиоиов путь (йашрйошап рагп) графа представляет собой простой путь, который проходит через каждую вершину ровно по одному разу.
Покажите, что язык НАМ-РАТН = ((С, и, е): в графе С имеется гамильтонов путь из и в с! принадлежит ХР. 34.2. 7 Покажите, что задачу о гамильтоновом пути в ориентированном ациклическом графе из упр. 34.2.6 можно решить в течение полиномиального времени. Сформулируйте эффективный алгоритм ее решения. 34.2.о Пусть ф — булева формула, составленная из булевых входных переменных хы хз,..., хы операторов НЕ (-), И (Л), ИЛИ (и) и скобок.
Формула ф называется тавтологией (запЮ!ойу), если для всех возможных наборов входных переменных в результате вычисления формулы получается значение Ь Определите язык булевых формул ТА()ТОЬОС т', состоящий из тавтологий. Покажите, что ТА()ТОЬОСвл' е со-ХР. 34.2.9 Докажите, что Р с со.гзР. 34.2.10 Докажите, что если МР ф со-гчР, то Р ф ХР. 34.2. 11 Пусть С вЂ” связный неориентированный граф, содержащий не менее трех вершин, а Сз — граф, полученный путем соединения всех пар вершин, которые связаны в графе С путем, длина которого не превышает трех ребер. Докажите, что граф Сз гамильтонов. (Указание: постройте остовное дерево графа С и воспользуйтесь иидукцией.) 34.3.
ХР-полнота н прпноднмость Пожалуй, одна из наиболее веских причин, по которым специалисты в области теории вычислительных систем полагают, что Р ~ ХЄ— наличие класса "ХР- И/б Часть ем'. Избранные темы полных" задач. Этот класс обладает замечательным свойством, которое состоит в том, что если хоть одну (любую) ХР-полную задачу можно решить в течение полиномиального времени, то и все задачи этого класса обладают решением за полиномиальное время, т.е.
Р = ХР. Однако, несмотря на многолетние исследования, до сих пор не обнаружено ни одного алгоритма с полиномиальным временем работы ни для одной ХР-полной задачи. Язык НАМ-СУС(Š— одна из ХР-полных задач. Если бы этот язык можно было распознать за полиномиальное время, то каждую задачу из класса ХР можно было бы решить в течение полиномиального времени. Фактически, если бы множество ХР— Р оказалось непустым, то с уверенностью можно было бы утверждать, что НАМ-СУС1 Е е ХР— Р.
В определенном смысле ХР-полные языки — "самые сложные" в классе ХР. В этом разделе будет показано, как относительная "сложность" языков сравнивается с помощью точного понятия под названием "приводимость за полиномиальное время". Затем приводится формальное определение ХР-полных языков, а в конце раздела дается набросок доказательства того, что один из таких языков — С1НС(ЛТ-БАТ вЂ” является ХР-полным. В разделах 34.4 и 34.5 с помощью понятия приводимости демонстрируется, что многие другие задачи также являются ХР-полными. Приводимость Интуитивно понятно, что задачу я можно свести к другой задаче („у, если любой экземпляр задачи 1,1 "легко перефразируется" в экземпляр задачи Я', решение которого позволяет получить решение соответствующего экземпляра задачи („1. Например, задача решения линейных уравнений относительно неизвестной величины х сводится к задаче решения квадратных уравнений. Если задан экземпляр ах + 6 = О, его можно преобразовать в уравнение Охз + ах + Ь = О, решение которого совпадает с решением уравнения ах + б = О.
Таким образом, если задача 1,1 сводится к другой задаче (г', то решить задачу ьг в некотором смысле "ие сложнее", чем задачу Я'. Возвращаясь к применению системы формальных языков для решения задач, будем говорить, что язык Ь| приводим за полинвмиальное время (ро!упоппа!- йпе гедпс(Ые) к языку Ьз (что обозначается как Ь| <р Хз, если существует вычислимая за полиномиальное время функция 1: (О, 1)* — ь (О, 1)*, такая что для всех х е (О, 1)" х е Ьз тогда и только тогда, когда 1(х) Е Ьз . (34.1) Функцию 1' называют функцией приведения (гедисйоп йшс1юп), а алгоритм г с полиномиальным временем работы, вычисляющий функцию 1, — алгоритмам приведения (гедисйоп а! копбпп).
На рис. 34.4 проиллюстрировано приведение языка Ь1 к другому языку Тз за полиномиальное время. Каждый язык — зто подмножество множества (О, 1)*. Функция приведения 1 обеспечивает такое отображение за полиномиальное время, что если т е Ьп то 1(х) е Ьз. Кроме того, если х ф Еп то Дх) ф Ьз. Таким Рдело 34 ХР-лолпото 1117 Х юстрация к приведению за полиномиальное время языка Е,г к языку Ьз с помощью ения 1. Для любых входных данных к б (О, 1) вопрос о том, справедливо ли б со имеет тот ие ответ, что и вопрос о справедливости 1(к) е ьз. Рис. 34А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
