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