Алгоритмы - построение и анализ (1021735), страница 229
Текст из файла (страница 229)
Покажите, что если НАМ С~'с~.в Е Р, то задача о выводе списка вершин гамильтонового цикла в порядке их обхода разрешима в течение полиномиального времени. 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 ХР-полнота и приводимость По-видимому, одна из веских причин, по которым специалисты в области теории вычислительных систем полагают, что Р ф ХР, — наличие класса "ХР- полных" задач. Этот класс обладает замечательным свойством, которое состоит в том, что если хоть одну (любую) ХР-полную зацачу можно решить в течение полиномиального времени, то и все задачи этого класса обладают полиномиальновременным решением, т.е.
Р = ХР. Однако, несмотря на многолетние исследования, до сих пор не обнаружено ни одного алгоритма с полиномиальным временем работы ни для одной ХР-полиой задачи. Язык НАм Сусек — одна из ХР-полных зацач. Если бы этот язык можно было бы распознать за полиномиальное время, то каждую задачу из класса ХР можно было бы решить в течение полиномиального времени. Фактически, если бы множество ХР— Р оказалось непустым, то с уверенностью можно было бы утверждать, что НАм СУСИ Е ХР— Р. В определенном смысле ХР-полные языки — "самые сложные*' в классе ХР. В этом разделе будет показано, как относительная "сложность" языков сравнивается с помощью точного понятия под названием "приводимость к полиномиальному времени".
Затем приводится формальное определение ХР-полных языков, а в конце раздела дается набросок доказательства того, что один из таких языков с именем Саси~т БАт, является ХР-полным. В разделах 34.4 и 34.5 с помощью понятия приводимости демонстрируется, что многие другие задачи также ХР- полные. Прииодимость Интуитивно понятно, что задачу (г' можно свести к другой задаче ьг', если любой экземпляр задачи (г "легко перефразируется" в экземпляр задачи Я', решение Глава 34. МР-полнота 1107 Рис. 34.4. Иллюстрация к приведению в течение поливомиальвого времеви языка Ь| к языку Ьз с помощью функции приведения т которого позволяет получить решение соответствующего экземпляра задачи Я.
Например, задача решения линейных уравнений относительно неизвестной величины х сводится к задаче решения квадратных уравнений. Если задан экземпляр ах+ 6 = О, его можно преобразовать в уравнение Охз + ах + 6 = О, решение которого совпадает с решением уравнения ах+ Ь = О. Таким образом, если задача (~ сводится к другой задаче Я', то решить задачу Я в некютором смысле "не сложнее", чем задачу Я'.
Возвратимся к применению системы формальных языков для решения задач. Говорят, что язык Ь| приводим в течение полиномиального времени (ро! употЫ- пше гесйс1Ые) к языку Бз (что обозначается как Б| <р Бз), если существует вычислимая за полиномиальное время функция 1: (О, 1)' -+ 10, 1)', такая что для всех х Е (О, 1) х Е Б~ тогда и только тогда, когда 1 (х) Е Ьз. (34.1) Функцию Г' называют функцией приведения (гедпсцоп йшс11оп), а алгоритм Г с полиномиальным временем работы, вычисляющий функцию г, — авгорииьиом приведения (гедпсйоп а1яопг)пп). Рнс. 34.4 иллюстрирует понятие приведения языка Б| к другому языку Бз в течение полиномиального времени.
Каждый язык — это подмножество множества (О, 1)'. Функция приведения т" обеспечивает такое отображение в течение полиномиального времени, что если х Е Бп то Г" (х) Е Бз. Более того, если х ф Ьм то г" (х) 11 Ез. Таким образом, функция приведения отображает любой экземпляр х задачи принятия решения, представленной языком Ьы на экземпляр г" (х) задачи, представленной языком Бз.
Ответ на вопрос о том, принадлежит ли экземпляр ~ (х) языку Ьз, непосредственно позволяет ответить на вопрос о том, принадлежит ли экземпляр х языку Бп Часть Ч11. Избранные темы 1108 Рис. 34.5. Иллюстрация к доказательству леммы 34.3 Приведение в течение полиномиального времени служит мощным инструментом доказательства того, что различные языки принадлежат классу Р. Лемма 34.3. Если Ьы Ьз С (О, Ц* — языки, такие что Ь1 <р Ьз, то из Ьз Е Р следует Ьг е Р. Доказаливзьстао. Пусть Аз — алгоритм с полиномиальным временем выполнения, который распознает язык Ьз, а à — полиномиально-временной алгоритм приведения, вычисляющий приводящую функцию г".
Построим алгоритм А| с полиномиальным временем выполнения, который распознает язык Ь|. На рис. 34.5 проиллюстрирован процесс построения алгоритма А1. Для заданного набора входных данных х е (О, Ц' в алгоритме А1 с помощью алгоритма Р данные х преобразуются в г' (х), после чего с помощью алгоритма Аз проверяется, является ли г" (х) Е Ьз. Результат работы алгоритма Аз выводится алгоритмом А1 в качестве ответа. Корректность алгоритма А1 следует из условия (34.1).
Алгоритм выполняется в течение полиномиального времени, поскольку и алгоритм Р, и алгоритм Аз завершают свою работу за полиномиальное время (см. упражнение 34.1-5). д 1з1Р-Полнота Приведения в течение полиномиального времени служат формальным средством, позволяющим показать, что одна задача такая же по сложности, как и другая, по крайней мере с точностью до полиномиально-временного множителя. Другими словами, если Ь1 <р Ьз, то сложность языка Т,1 превышает сложность языка Ьз не более чем на полиномиальный множитель, Вот почему отношение "меньше или равно" для приведения является мнемоническим.
Теперь можно определить множество ХР-полных языков, являющихся самыми сложными задачами класса ХР. Язык Ь С (О, Ц' является ХР-полным (ХР-сошр!е1е), если выполняются перечисленные ниже условия: 1. БЕАР,и 2. Ь' <р Ь для всех Т' Е МР. Глава 34. МР-полнота 1109 Рис. 34.6. Представление большинства специалистов в области вычислительных систем об отношении между классами Р, МР и МРС; классы Р и МРС полностью содержатся в классе МР, и Р и МРС = 6 Если язык Б удовлетворяет свойству 2, но не обязательно удовлетворяет свойству 1, говорят, что Ь вЂ” ЮР-сложный (МР-Ьаго).
Определим также класс ХРС как класс ХР-полных языков. Как показано в приведенной далее теореме, МР-полнота — ключевая проблема в разрешении вопроса о том, равны ли на самом деле классы Р и МР. Теорема 34.4. Если некоторая ХР-полная задача разрешима в течение полиномиального времени, то Р = МР. Это эквивалентно утверждению„что если какая- нибудь задача из класса ХР не решается в течение полиномиального времени, то никакая из ХР-полных задач не решается в течение полиномнального времени.
Доказашвиьсиво. Предположим, что Ь Е Р и что й Е МРС. Для любого языка Т,' Е Е ХР, согласно свойству 2 определения МР-полноты, справедливо Ь' <р Б. Таким образом, в соответствии с леммой 34.3, мы также имеем Ь' Е Р, что и доказывает первое утверждение теоремы. Чтобы доказать второе утверждение, заметим, что оно является переформулировкой первого. Вот почему при исследовании вопроса Р ф ХР внимание акцентируется на ХР-полных задачах. Большинство специалистов по теории вычислительных систем полагают, что Р ф ХР, так что отношения между классами Р, ХР и ХРС являются такими, как показано на рис. 34.6.
Но если кто-нибудь додумается до алгоритма с полиномиальным временем работы, способного решить ХР-полную задачу, тем самым будет доказано, что Р = ХР. Тем не менее, поскольку до сих пор такой алгоритм не обнаружен ни для одной ХР-полной задачи, доказательство ХР-полноты задачи является веским свидетельством ее трудноразрешимости. Часть Ч!!. Избранные темы 1110 Выполнимость схем Определение ХР-полноты уже сформулировано, но до сих пор не была доказана ХР-полнота ни одной задачи. Как только это будет сделано хотя бы для одной задачи, с помощью приводимости в течение полиномиального времени можно будет доказать ХР-полноту других задач.
Таким образом, сосредоточим внимание на том, чтобы продемонстрировать ХР-полноту задачи о выполнимости схем. К сожалению, для формального доказательства того, что задача о выполнимости схем является ХР-полной, требуются технические детали, выходящие за рамки настоящей книги. Вместо этого мы дадим неформальное описание доказательства, основанного на базовом понимании булевых комбинационных схем. Булевы комбинационные схемы составляются из булевых комбинационных элементов, соединенных между собой проводами. Булав камбинаиионный элемент (Ъоо1еап сощЪ!лайопа! е1ещепг), или каибинаиионный логический элемент, — это любой элемент сети, обладающий фиксированным количеством булевых входов и выходов, который выполняет вполне определенную функцию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
