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