Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 225
Текст из файла (страница 225)
Однако методология аналогична в том отношении, что доказательство ХР-полноты задачи В основывается на предположении о ХР-полноте задачи А. Первая ХР-полная задача Поскольку метод приведения базируется на том, что для какой-то задачи заранее известна ее ХР-полнота, то для доказательства ХР-полноты различных задач нам понадобится "первая" ХР-полная задача. В качестве таковой мы воспользуемся задачей, в которой задана булева комбинационная схема, состоящая из логических элементов И, ИЛИ и НЕ. В задаче спрашивается, существует ли для этой схемы такой набор входных булевых величин, для которого будет выдано значение 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 (нет).
Многие абстрактные задачи являются не задачами принятия решения, а задачами олшимизации (орйппгайоп ргоЫешз), в которых некоторое значение подлежит минимизации или максимизации. Однако ранее мы убедились, что обычно не составляет труда сформулировать задачу оптимизации как задачу принятия решения, которая не сложнее исходной. Кодирование Если абстрактная задача решается с помощью компьютерной программы, экземпляры задач необходимо представить в виде, понятном этой программе. Кгздированые (епсосйпй) множества Я абстрактных объектов — это отображение е множества Я на множество бинарных строкз. Например, всем известно, что натуральные числа 1ь( = (1, 2,...) кодируются строками (1, 10, 11,...).
В этой кодировке е (17) = 10001. Каждый, кто интересовался, как в компьютере представляются символы клавиатуры, знаком с кодами АБСП или кодами ЕВС131С. В кодировке АБСП представление символа А выглядит как 1000001. В виде бинарной строки можно закодировать даже составной объект. Для этого юнструируется комбинация, состоящая из представлений элементов, которые содержит в себе этот объект. Многоугольники, графы, функции, ориентированные пары, программы — все это можно заюдировать бинарными строками. Таким образом, компьютерный алгоритм, который "решает"' некоторую абстрактную задачу принятия решения, фактически принимает в качестве входных данных закодированный экземпляр задачи. Назовем задачу, множество зОбласть значений отображения е — не обязательно бяяаряме строки; подойдет любое множество строк, состоящих из символов конечного алфавита, содержащего не менее двух символов.
1094 Часть Ч!1. Избранные темы экземпляров которой является множеством бинарных строк, кон«ретной (сопсге(е ргоЫеш). Говорят, что алгоритм решает (зо1чез) конкретную задачу в течение времени 0 (Т (гз)), если для заданного экземпляра задачи з длиной п = ~з~ с его помощью можно получить решение в течение времени 0 (Т (п))~. Поэтому конкретная задача разрешима в течение нолинаниального времени (ро1упоппа1мппе зо1уаЫе), если существует алгоритм, позволяющий решить ее за время О (гз~), где lс — некоторая ыэнстаита.
Теперь класс сложности Р (сошр!ех(гу с1азз Р) можно формально определить как множество конкретных задач принятия решения, разрешимых в течение полиномиального времени. С помощью кодирования абстрактные задачи можно отображать на конкретные. Данную абстрактную задачу принятия решения Я, отображающую множество экземпляров на множество (О, Ц, с помощью кодирования е: Х -+ (О, Ц можно свести к связанной с ней конкретной задаче принятия решения, которая будет обозначаться как е (Я)4.
Если Я (з) Е (О, Ц вЂ” решение экземпляра абстрактной задачи з б 1, то оно же является и решением экземпляра конкретной задачи е(з) Е (О, Ц'. Заметим, что некоторые бинарные строки могут не представлять осмысленного экземпляра абстрактной задачи. Для удобства мы будем предполагать, что любая такая строка произвольным образом отображается на О. Таким образом, конкретная задача имеет те же решения, что и абстрактная, если ее экземпляры в виде бинарных строк представляют закодированные экземпляры абстрактной задачи.
Попытаемся расширить определение разрешимости в течение полиномиального времени для конкретных задач на абстрактные задачи, воспользовавшись в качестве связующего звена кодами; однако хотелось бы, чтобы определение не зависело от вида кодировки. Другими словами, эффективность решения задачи не должна зависеть от того, как она кодируется. К сожалению, на самом деле существует достаточно сильная зависимость от кодирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
