Алгоритмы - построение и анализ (1021735), страница 225
Текст из файла (страница 225)
Это преобразование занимает полиномиальное время. 2. Ответы являются идентичными, т.е. в экземпляре а ответ "да" выдается тогда и только тогда, когда в экземпляре,9 тоже выдается ответ "да". Часть ЧП. Избранные темы 1090 и ~ Г: ~Горреяррмрсеи-; р1 д, йдррррйррвйБвраае-.~ '.*~.-р4-з лр — --з р — р;; 'свааррзмрмьррч'"-:;.,~ — — рз ~ рюдсррарррьиммам.: ( ".л.и~бйл~йм'::4 ~.=:-:рл~."жной -' 1.~--,-,—;-~.-~- нр А ргрррьч лрялртря ~ оррррз Х р рорялочлррн ыя ррьяррьч раины Рис.
34.1. Решение задачи принятия решения А в течение полиномнального времени с помощью алгоритма приведения с полиномнальным временем работы и известною алгоритма с полиномиальным временем работы, предназначенного для решения другой задачи В Назовем такую процедуру алгориюимарн приведения (гедпсйоп а1яопйт) с полиномиальным временем. Как видно из рис. 34.1, эта процедура предоставляет описанный ниже способ решения задачи А в течение полиномиального времени.
1. Заданный экземпляр ср задачи А с помощью алгоритма приведения с полиномиальным временем преобразуется в экземпляр й3 задачи В. 2. Запускается алгоритм, решающий экземпляр 13 задачи принятия решения В в течение полиномиального времени. 3. Ответ для экземпляра,д используется в качестве ответа для экземпляра ср. Поскольку для выполнения каждого из перечисленных выше этапов требуется полиномиальное время, это относится и ко всему процессу в целом, что дает способ решения экземпляра ср задачи в течение полиномиального времени. Другими словами, путем сведения задачи А к задаче В "простота" задачи В используется для доказательства "простоты" задачи А.
Если вспомнить, что при доказательстве ХР-полноты требуется показать, насколько сложной является задача, а не насколько она простая, доказательство МР- полноты с помощью приведения с полиномиальным временем работы выполняется обратно описанному выше способу. Продвинемся в разработке этой идеи еще на шаг и посмотрим, как с помощью приведения с полиномиальным временем показать, что для конкретной задачи В не существует алгоритмов с полиномиальным временем работы. Предположим, что имеется задача принятия решения А, относительно которой заранее известно, что для нее не существует алгоритма с полиномиальным временем работы. (Пока что мы не станем обременять себя размышлениями о том, как сформулировать такую задачу А.) Предположим также, что имеется преобразование, позволяющее в течение полиномиального времени преобразовать экземпляры задачи А в экземпляры задачи В.
Теперь с помощью простого доказательства "от противного" можно показать, что для решения задачи В не существует алгоритмов с полиномиальным временем работы. Предположим обратное, т.е. что существует решение задачи В в виде алгоритма с полиномиальным временем работы. Тогда, воспользовавшись методом, проиллюстрированным на рис. 34.1, можно получить способ решения задачи А в течение полиномиаль- Глава 34. МР-полнота 1091 ного времени, а это противоречит предположению о том, что таких алгоритмов для задачи А не существует.
Если речь идет о ХР-полноте, то здесь нельзя предположить, что для задачи А вообще не существует алгоритмов с полиномиальным временем работы. Однако методология аналогична в том отношении, что доказательство ХР-полноты задачи В основывается на предположении о ХР-полноте задачи А. Первая ХР-полная задача Поскольку метод приведения базируется на том, что для какой-то задачи заранее известна ее ХР-полнота, то для доказательства ХР-полноты различных задач нам понадобится "первая" ХР-полная задача.
В качестве таковой мы воспользуемся задачей, в которой задана булева комбинационная схема, состоящая из логических элементов И, ИЛИ и НЕ. В задаче спрашивается, существует ли для этой схемы такой набор входных булевых величин, для которого будет выдано значение 1. Доказательство ХР-полноты этой первой задачи будет представлено в разделе 34.3. Краткое содержание главы В этой главе изучаются аспекты ХР-полноты, которые непосредственно основываются на анализе алгоритмов. В разделе 34.1 формализуется понятие "задачи" и определяется класс сложности Р как класс задач принятия решения, разрешимых в течение полиномиального времени. Также станет понятно, как эти понятия укладываются в рамки теории формальных языков.
В разделе 34.2 определяется класс ХР, к которому относятся задачи принятия решения, правильность решения которых можно проверить в течение полиномиального времени. Здесь также формально ставится вопрос Р ф ХР. В разделе 34.3 показано, как с помощью приведения с полиномиальным временем работы изучаются взаимоотношения между задачами. Здесь дано определение ХР-полноты и представлен набросок доказательства того, что задача о выполнимости схемы является ХР-полной. Имея одну ХР-полную задачу, в разделе 34.4 мы увидим, как можно существенно проще доказать ХР-полноту других задач с помощью приведения. Эта методология проиллюстрирована на примере двух задач на выполнимость формул, для которых доказывается ХР-полнота.
В разделе 34.5 ХР-полнота демонстрируется для широкого крута других задач. 34.1 Полиномиальное время Начнем исследование ХР-полноты с формализации понятия задач, разрешимых в течение полиномиального времени. Эти задачи считаются легко разрешимыми, Часть Ч[!. Избранные темы 1092 но не из математических, а из философских соображений. В поддержку этого мнения можно привести три аргумента.
Во-первых, хотя и разумно считать трудноразрешимой задачу, для решения которой требуется время 9 (гтгпо), на практике крайне редко встречаются задачи, время решения которых выражается полиномом такой высокой степени. Для практических задач, которые решаются за полиномиальное время, показатель степени обычно намного меньше. Опыт показывает, что если для задачи становится известен алгоритм с полиномиальным временем работы, то зачастую впоследствии разрабатывается и более эффективный алгоритм.
Даже если самый лучший из известных на сегодняшний день алгоритмов решения задачи характеризуется временем О [гьгоо), достаточно велика вероятность того, что скоро будет разработан алгоритм с намного лучшим временем работы. Во-вторых, для многих приемлемых вычислительных моделей задача, которая решается в течение полиномиального времени в одной модели, может быть решена в течение полиномиального времени и в другой.
Например, в большей части книги рассматривается класс задач, разрешимых в течение полиномиального времени с помощью последовательных машин с произвольной выборкой. Этот класс совпадает с классом задач, разрешимых в течение полиномиального времени на абстрактных машинах Тьюринга'. Он также совпадает с классом задач, разрешимых в течение полиномиального времени на параллельных компьютерах, если зависимость количества процессоров от объема входных данных описывается полиномиальной функцией.
В-третьих, класс задач, разрешимых в течение полиномиального времени, обладает полезными свойствами замкнутости, поскольку множество полиномов замкнуто относительно операций сложения, умножения и композиции. Например, если выход одного алгоритма с полиномиальным временем работы соединить со входом другой такой задачи, то получим полиномиальный составной алгоритм. Если же в другом алгоритме с полиномиальным временем работы фиксированное количество раз вызываются подпрограммы с полиномиальным временем работы, то время работы такого составного алгоритма также является полиномиальным. Абстрактные задачи Чтобы получить понятие о классе задач, разрешимых в течение полиномиального времени, сначала необходимо формально описать само понятие "задача".
Определим абсгпракгпную задачу (аЬз(гас( ргоЫеш) Я как бинарное отношение между множеством экземпляров [гпз1апсез) задач 1 и множеством решений [зо!ийопз) задач Я. Например, экземпляр задачи Бноктезт РАтн состоит из трех элементов: графа и двух вершин. Решением этой задачи является последовательность 'Подробное рассмотрение модели Тьюринга можно найти а книгах Хопкрофта (Норсгой) н Ульмана ((Л!гпап) [156), а также Льюиса (1еипа) и Пападимитриу (Рарайгп)ггюп) [204). Глава 34.
ИР-полнота 1093 вершин графа; при этом пустая последовательность может означать, что искомого пути не существует. Сама задача Яноктбзт Рдтн представляет собой отношение, сопоставляющее каждому экземпляру графа и двум его вершинам кратчайший путь по графу, соединяющий эти две вершины. Поскольку кратчайший путь может быть не единственным, юнкретный экземпляр задачи может иметь несколько решений. Представленная выше формулировка абстрактной задачи носит более широкий характер, чем требуется для наших целей.
Как мы уже убедились, теория НР-полноты ограничивается рассмотрением задач принятия решения (бесгз(оп ргоЫешз), требующих решения вида "да-нет". В этом случае абстрактную задачу принятия решения можно рассматривать как функцию, отображающую экземпляр множества 1 на множество решений (О, 1). Например, задача принятия решения, соответствующая задаче Зноктвзт РАтн, — рассмотренная выше задача РАтн. Если з = (О, и,гг, гс) — экземпляр задачи принятия решения РАтн, то равенство РАтн (з) = 1 (да) выполняется, если количество ребер в кратчайшем пути из вершины и в вершину гг не превышает Й; в противном случае РАтн(з) = 0 (нет). Многие абстрактные задачи являются не задачами принятия решения, а задачами олшимизации (орйппгайоп ргоЫешз), в которых некоторое значение подлежит минимизации или максимизации.
Однако ранее мы убедились, что обычно не составляет труда сформулировать задачу оптимизации как задачу принятия решения, которая не сложнее исходной. Кодирование Если абстрактная задача решается с помощью компьютерной программы, экземпляры задач необходимо представить в виде, понятном этой программе. Кгздированые (епсосйпй) множества Я абстрактных объектов — это отображение е множества Я на множество бинарных строкз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
