Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 244
Текст из файла (страница 244)
Не предпринимается попыток доказать, что существуют эффективные алгоритмы. Скорее, мы пытаемся доказать, что эффективных алгоритмов, вероятнее всего, не существует. В этом смысле доказательство ХР-полноты несюлько напоминает представленное в разделе 8.1 доказательство того, что нижняя зраница любого алгоритма, работающего по методу сравнений, равна Й(п 18п). Однако методы, используемые для доказательства ХР-полноты, отличаются от методов с применением дерева решений, описанных в разделе 8.1. Глава 34.
НР-аалваиа !099 При доказательстве ХР-полноты задачи используются трн ключевые концепции, описанные ниже. Задачи принятия решения и задачи оптимизации Многие представляющие интерес задачи являются задачами оптимизации (орг|пнхаГ|оп ргоЪ|ешз), каждому допустимому (" законному" ) решению которых можно сопоставить некоторое значение и для которых нужно найти допустимое решение с наилучшим значением. Например, в задаче поиска кратчайшего пути задаются неориентированный граф С, а также вершины и и с, и нужно найти путь из вершины и к вершине с, в котором содержится наименьшее количество ребер.
(Другимн словами, зто задача поиска кратчайшего пути между парой вершин невзвешенного неориентированного графа.) Однако ХР-полнота непосредственно применима не к задачам оптимизации, а к задачам принятия решения (бес|мол ргоЪ|ешз), в которых ответ может быть положительным или отрицательным (говоря более формально, принимать значения "1" или "0"), Хотя при доказательстве ХР-полноты задачи приходится ограничиваться задачами принятия решения, между ними и задачами оптимизации существует удобная взаимосвязь. Наложив ограничение на оптимизируемое значение, поставленную задачу оптимизации можно свести к соответствующей задаче принятия решения.
Например, задаче поиска кратчайшего пути соответствует задача принятия решения о существовании пути: существует ли для заданных исходных данных, в число которых входит направленный граф С, вершины и и с и целое число |г, путь из вершины и к вершине с, состоящий не более чем из |г ребер? Взаимосвязь между задачей оптимизации и соответствующей ей задачей принятия решения полезна для нас, если мы пытаемся показать, что задача оптимизации является "сложной". Причина зтого заключается в том, что задача принятия решения в некотором смысле "проще", или по крайней мере "не сложнее'*.
Например, задачу о существовании пути можно решить, решив задачу поиска кратчайшего пути, а затем сравнив количество ребер в найденном кратчайшем пути со значением параметра к в задаче принятия решения. Другими словами, если задача оптимизации простая, соответствующая ей задача принятия решения также простая.
Формулируя это утверждение так, чтобы оно имело большее отношение к ХР-полноте, можно доказать, что если удается засвидетельствовать сложность задачи принятия решения, это означает, что соответствующая задача оптимизации также сложная. Таким образом, хотя и приходится ограничиваться рассмотрением задач принятия решения, теория ХР-полногы зачастую имеет следствия и для задач оптимизации. Приведение Сделанное выше замечание о том, что одна задача не сложнее нли не легче другой, применимо, даже если обе задачи являются задачами принятия решения. Эта идея используется почти во всех доказательствах ХР-полноты.
Это делается следующим образом. Рассмотрим задачу принятия решения, скажем, задачу А, которую хотелось бы решить в течение полиномиального времени. Назовем «100 Часть И1 Избранные темы Эюемлляр а ', ««лгорйтг«гяязледенг«к; Экммш|яр р 1„: Алгоритм пркншзгя: =-э'.
э- да з ~~ А ~ ~ ' - .знг«ш'.мшьный "~: . 0 «юн".-"".ш-:".-'!«'"чв«шш" 1--- ~- и ~ . ' Дзеьжкьчк «жХ2Ы, а%8«ьм Вфьмй6Я, Ра««отьт Иег ь морктм пршьзт ю рс1лешш А с полююмнап пыл временем «~а«ю ш Рнс. 34.1. Использоаанне алгоритма прнаедення с полнномнальным временем работы для решення задачи принятия решения А за полнномнальное время прн навнчнн алгоритма с полнномлальным временем работы, решмощего некоторую другую задачу В. Эюемпляр о задачи А преобразуется за полнномнальное время в экземпляр Д эадачн В, после чего задача В решается эа полнномнальное время, н ответ для экземпляра В нспользушся как ответ для экземпляра о. входные данные отдельно взятой задачи энзеыплярои (1пз«апсе) этой задачи.
Например, экземпляром задачи существования пути является некоторый граф С, некоторые его вершины и и и, а также нем«торос целое число lс. А теперь предположим, что существует другая задача принятия решения, скажем, В, для которой заранее известно, как решить ее в течение полиномиального времени. Наконец предположим, что имеется процедура с приведенными ниже характеристиками, преобразующая любой экземпляр гт задачи А в некоторый экземпляр «3 задачи В.
Преобразование выполняется за полиномиальное время. ° Ответы являются идентичными, т.е. в экземпляре гг ответ "да" выдается тогда и только тогда, когда в экземпляре «3 также выдается ответ "да". Назовем такую процедуру алгоритмам приведения (гебпсбоп а1йопбпп) с полиномиальным временем.
Как видно из рис. 34.1, эта процедура предоставляет описанный ниже способ решения задачи А за полиномиальное время. 1. Заданный экземпляр ст задачи А с помощью алгоритма приведения с полиномиальным временем преобразуется в экземпляр «3 задачи В. 2. Запускается алгоритм, решающий экземпляр ~9 задачи принятия решения В в течение полиномиального времени. 3. Ответ для экземпляра «3 используется в качестве ответа для экземпляра ст.
Поскольку для выполнения каждого из перечисленных выше этапов требуется полиномиальное время, это относится и ко всему процессу в целом, что дает способ решения экземпляра о задачи за полиномиальное время. Другими словами, путем приведения задачи А к задаче В "простота" задачи В используется для доказательства "простоты" задачи А. Если вспомнить, что при доказательстве «з«Р-полноты требуется показать, насколько сложной, а не насколько простой является задача, доказательство ХР-полноты с помощью приведения с полиномиальным временем работы выполняется обратно описанному выше способу. Продвинемся в разработке этой идеи еще на шаг и посмотрим, как с помощью приведения с полиномиальным временем показать, что для конкретной задачи В не существует алгоритмов с полиномиальным временем работы.
Предположим, что имеется задача принятия решения А, относительно которой заранее известно, что для нее не существует алгоритма с по- !!О! Глава 34. ИР-лолната линомиальным временем работы. (Пока что мы не станем обременять себя размышлениями о том, как сформулировать такую задачу А.) Предположим также, что имеется преобразование, позволяющее в течение полиномиального времени преобразовать экземпляры задачи А в экземпляры задачи В.
Теперь с помощью простого доказательства "от противного" можно показать, что для решения задачи В не существует алгоритмов с полиномиальным временем работы. Предположим обратное, т.е. что существует решение задачи В в виде алгоритма с полиномиальным временем работы. Тогда, воспользовавшись методом, проиллюстрированным на рис. 34А, можно получить способ решения задачи А в течение полиномнального времени, а это противоречит предположению о том, что таких алгоритмов для задачи А не существует.
Если речь идет о ХР-полноте, то здесь нельзя предположить, что для задачи А вообще не существует алгоритмов с полиномиальным временем работы. Однако методология аналогична в том отношении, что доказательство ХР-полноты задачи В основывается на предположении об ХР-полноте задачи А. Первая МР-ладная задача Поскольку метод приведения основан на том, что для какой-то задачи заранее известна ее ХР-полнота, то для доказательства ХР-полноты различных задач понадобится "первая" ХР-полная задача. В качестве таковой воспользуемся задачей, в которой задана булева комбинационная схема, состоящая из логических элементов И, ИЛИ и НЕ.
В задаче спрашивается, существует ли для этой схемы такой набор входных булевых величин, для которого будет выдано значение 1. Доказательство ХР-полноты этой первой задачи будет представлено в разделе 34.3. Краткое содержание главы В этой главе изучаются аспекты ХР-полноты, которые непосредственно основываются на анализе алгоритмов. В разделе 34.1 формализуется понятие "задачи" и определяется класс сложности Р как класс задач принятия решения, разрешимых в течение полиномиального времени.
Также станет ясно, как эти понятия укладываются в рамки теории формальных языков. В разделе 34.2 определяется класс ХР, к которому относятся задачи принятия решения, правильность решения которых можно проверить в течение полиномиального времени. Здесь также формально ставится вопрос Р Р ХР.
В разделе 34.3 показано, как с помощью приведения с полиномиальным временем работы изучаются взаимоотношения между задачами. Здесь дано определение ХР-полноты и представлен набросок доказательства того, что задача "о выполнимости схемы" является ХР-полной. Имея одну ХР-полную задачу, в разделе 34.4 мы увидим, как можно существенно проще доказать ХР-полноту других задач с помощью приведения. Эта методология проиллюстрирована на примере двух задач на выполнимость формул, для которых доказывается ХР-полнота. В разделе 34.5 ХР-полнота демонстрируется для широкого круга других задач.
Ибг Часть РИ. Избранные тены 34.1. Полиномиальное время Начнем изучение ]ЧР-полноты с формализации понятия задач, разрешимых в течение полиномиапьного времени. Зти задачи считаются легко разрешимыми, но не из математических, а из философских соображений. В поддержку этого мнения можно привести три аргумента. Во-первых, хотя и разумно считать трудноразрешимой задачу, для решения которой требуется время 9(п)бо), на практике крайне редко встречаются задачи, время решения которых выражается полиномом таюй высокой степени. Для практических задач, которые решаются за полиномиапьное время, показатель степени обычно намного меньше. Опыт показывает, что если для задачи становится известен алгоритм с полиномиальным временем работы, то зачастую впоследствии разрабатывается и более эффективный алгоритм. Даже если самый лучший из известных на сегодняшний день алгоритмов решения задачи харшперизуется временем аЗ(п)оо), достаточно высока вероятность того, что всюре будет разработан алгоритм с намного лучшим временем работы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
