Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 224

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 224)

Любая задача класса Р принадлежит классу ХР, поскольку принадлежность задачи классу Р означает, что ее решение можно получить в течение полиномиального времени, даже не располагая сертификатом. Это замечание будет формализовано ниже в данной главе, а пока что можно считать, что Р С ХР. Остается открытым вопрос, является ли Р строгим подмножеством ХР. Неформально задача принадлежит классу ХРС (такие задачи называются МР- лолными (ХР-сотр1е1е)), если она принадлежит классу ХР и является такой же "сложной", как и любая задача из класса ХР.

Ниже в этой главе будет дано формальное определение того, что означает выражение "задача такая же по сложности, как любая задача из класса ХР". А пока что мы примем без доказательства положение, что если любую ХР-полную задачу можно решить в течение полиномиального времени, то для каждой задачи из класса ХР существует алгоритм с полиномиальным временем работы. Большинство ученых, занимающихся теорией вычислительных систем, считают ХР-полные задачи очень трудноразрешимыми, потому что при огромном разнообразии изучавшихся до настоящего времени ХР- полных задач ни для одной из них пока так и не найдено решение в виде алгоритма с полиномиальным временем работы.

Таким образом, было бы крайне удивительно, если бы все они оказались разрешимыми в течение полиномиального времени. Чтобы стать квалифицированным разработчиком алгоритмов, необходимо понимать основы теории ХР-полноты. Если установлено, что задача ХР-полная, это Часть ЧП. Избранные темы 1088 служит достаточно надежным указанием на то, что она трудноразрешимая.

Как инженер, вы эффективнее потратите время, если займетесь разработкой приближенного алгоритма (см. главу 35) или решением легкого особого случая, вместо того, чтобы искать быстрый алгоритм, выдающий точное решение задачи. Более того, многие естественно возникающие интересные задачи, которые на первый взгляд не сложнее задачи сортировки, поиска в графе или определения потока в сети, фактически являются ХР-полными.

Таким образом, важно ознакомиться с этим замечательным классом задач. Как показать, что задача является 1чР-полпой Методы, позволяющие доказать, что та или иная задача является ХР-полной, отличаются от методов, которые использовались в большей части этой книги лля разработки и анализа алгоритмов. Имеется фундаментальная причина такого различия: чтобы показать, что задача является ХР-полной, делается утверждение о том, насколько она сложна (или, по крайней мере, насколько она сложна в нашем представлении), а не о том, насколью она проста.

Не предпринимается попыток доказать, что существуют эффективные алгоритмы. Скорее, мы пытаемся доказать, что эффективных алгоритмов, вероятнее всего, не существует. В этом смысле доказательство ХР-полноты несколько напоминает представленное в разделе 8.1 доказательство того, что нижняя граница любого алгоритма, работающего по методу сравнений, равна 11 (и 18 и).

Однако методы, использующиеся для доказательства ХР-полноты, отличаются от методов с применением дерева решений, описанных в разделе 8.1. При доказательстве ХР-полноты задачи используются три основные концепции, описанные ниже. Задачи принятия решения и задачи оптимизации Многие представляющие интерес задачи являются задачами оиюиимизаиии (ор11ш1хабоп ргоЫешз), каждому допустимому ("законному") решению которых можно сопоставить неюторое значение и для которых нужно найти допустимое решение с наилучшим значением.

Например, в задаче, получившей название Яноктвзт Рлтн, залается неориентированный граф С, а также вершины и и и, и нужно найти путь из вершины и к вершине о, в котором содержится наименьшее юличество ребер. (Другими словами, Бнокткзт РАтн — это задача поиска кратчайшего пути между парой вершин невзвешенного неориентированного графа.) Однако ХР-полнота непосредственно применима не к задачам оптимизации, а к задачам принятия реизенин (бес1з1оп ргоЫешз), в которых ответ может быть положительным или отрицательным (говоря более формально, принимать значения "Г' или "О"). Глава 34. МР-полнота 1089 Хотя при доказательстве НР-полноты задачи приходится ограничиваться задачами принятия решения, между ними и задачами оптимизации существует удобная взаимосвязь. Наложив ограничение на оптимизируемое значение, поставленную задачу оптимизации можно свести к соответствуюшей задаче принятия решения.

Например, задаче БНОктезт Рлтн соответствует задача принятия решения под названием Рлтн: существует ли для заданных исходных данных, в число которых входит направленный граф С, вершины и и о, и целое число Й, путь из вершины и к вершине о, состоящий не более чем из й ребер. Взаимосвязь между задачей оптимизации и соответствующей ей задачей принятия решения полезна для нас, если мы пытаемся показать, что задача оптимизации является "сложной". Причина этого заключается в том, что задача принятия решения в некотором смысле "проще" или, по крайней мере, "не сложнее".

Например, задачу Рати можно решить, решив задачу Зноктнзт Рлтн, а затем сравнивая количество ребер в найденном крагчайшем пути со значением параметра Й в задаче принятия решения. Другими словами, если задача оптимизации простая, соответствующая ей задача принятия решения тоже простая. Формулируя это утверждение так, чтобы оно имело большее отношение к МР-полноте, можно сказать, что если удается засвидетельствовать сложность задачи принятия решения, это означает, что соответствующая задача оптимизации тоже сложная. Таким образом, хотя и приходится ограничиваться рассмотрением задач принятия решения, теория МР-полноты зачастую имеет следствия и для задач оптимизации.

Приведение Сделанное выше замечание о том, что одна задача не сложнее или не легче другой, применимо, даже если обе задачи являются задачами принятия решения. Эта идея используется почти во всех доказательствах ИР-полноты. Это делается следующим образом. Рассмотрим задачу принятия решения, скажем, задачу А, которую хотелось бы решить в течение полиномиального времени. Назовем входные данные отдельно взятой задачи экземлляром (1пз1апсе) этой задачи. Например, экземпляром задачи Рлтн является некоторый граф С, некоторые его вершины и и о, а также некоторое целое число к.

А теперь предположим, что существует другая задача принятия решения, скажем, В, для которой заранее известно, как решить ее в течение полиномиального времени. Наконец, предположим, что имеется процедура с приведенными ниже характеристиками, преобразующая любой экземпляр а задачи А в некоторый экземпляр ~9 задачи В. 1. Это преобразование занимает полиномиальное время. 2. Ответы являются идентичными, т.е.

в экземпляре а ответ "да" выдается тогда и только тогда, когда в экземпляре,9 тоже выдается ответ "да". Часть ЧП. Избранные темы 1090 и ~ Г: ~ГорвеаиеГсеи-;:1 д, ййерл~йрявйБвраае-.~ '.*~.-~4-з Лз — --й ~ — ~;; 'свааечмвмьмж"-:;.,~ — — 'э ~ ю~юВсаоаиемиммам.: ".змайайЖйм,' """ ' " амйэжэййем"." " 1 Д~ Алшретм лаымтик ~ сиевл Х с мгиаоинвзи ыи зрмюич рийаы Рве.

34.1. Решение задачи принятия решения А в течение полнномнального времени с помощью алгоритма приведения с полнномнальным временем работы н известною алгоритма с полиномиальным временем работы, предназначенного для решения другой задачи В Назовем такую процедуру алгориюимаи приведения (гебпсйоп а!допй)ййп) с полиномиальным временем. Как видно из рис. 34.1, зта процедура предоставляет описанный ниже способ решения задачи А в течение полиномиального времени. 1. Заданный экземпляр а задачи А с помощью алгоритма приведения с полиномиальным временем преобразуется в экземпляр й3 задачи В. 2.

Запускается алгоритм, решающий экземпляр 13 задачи принятия решения В в течение полиномиального времени. 3. Ответ для экземпляра,в используется в качестве ответа для экземпляра а. Поскольку для выполнения каждого из перечисленных выше этапов требуется полиномиальное время, это относится и ко всему процессу в целом, что дает способ решения экземпляра а задачи в течение полиномиального времени. Другими словами, путем сведения задачи А к задаче В "простота" задачи В используется для доказательства "простоты" задачи А.

Если вспомнить, что при доказательстве ХР-полноты требуется показать, насколько сложной является задача, а не насколько она простая, доказательство МР- полноты с помощью приведения с полиномиальным временем работы выполняется обратно описанному выше способу. Продвинемся в разработке этой идеи еще на шаг и посмотрим, как с помощью приведения с полиномиальным временем показать, что для конкретной задачи В не существует алгоритмов с полиномиальным временем работы.

Предположим, что имеется задача принятия решения А, относительно которой заранее известно, что для нее не существует алгоритма с полиномиальным временем работы. (Пока что мы не станем обременять себя размышлениями о том, как сформулировать такую задачу А.) Предположим также, что имеется преобразование, позволяющее в течение полиномиального времени преобразовать экземпляры задачи А в экземпляры задачи В. Теперь с помощью простого доказательства "от противного" можно показать, что для решения задачи В не существует алгоритмов с полиномиальным временем работы. Предположим обратное, т.е. что существует решение задачи В в виде алгоритма с полиномиальным временем работы. Тогда, воспользовавшись методом, проиллюстрированным на рис.

34.1, можно получить способ решения задачи А в течение полиномиаль- Глава 34. МР-полнота 1091 ного времени, а это противоречит предположению о том, что таких алгоритмов для задачи А не существует. Если речь идет о ХР-полноте, то здесь нельзя предположить, что для задачи А вообще не существует алгоритмов с полиномиальным временем работы.

Характеристики

Список файлов книги