Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 230
Текст из файла (страница 230)
Для обозначения функции НЕ используется символ, для обозначения функции И— символ Л, а для обозначения функции ИЛИ вЂ” символ Ч. Например, О ~/ 1 = 1. Вентили И и ИЛИ можно обобщить на случай, когда входных значений больше двух. Выходное значение вентиля И равно 1, если все его входные значения равны 1; в противном случае его выходное значение равно О. Выходное значение вентиля ИЛИ равно 1, если хоть одно из его входных значений равно 1; в противном случае его выходное значение равно О. Булева комбинационная схема (Ъоо1еап сошЪ|пайопа! с(гсвй) состоит из одного или нескольких комбинационных логических элементов, соединенных проводами (ччгез). Провод может соединять выход одного элемента со входом другого, подавая таким образом выходное значение первого элемента на вход второго.
На рис. 34.8 изображеньз две похожие друг на друга булевы комбинационные схемы, отличающиеся лишь одним вентилем. В части а рисунка также приводятся значения, которые передаются по каждому проводу, если на вход подаются значения (хз = 1, хз = 1, хз = О). Хотя к одному и тому же проводу нельзя подключить более одного вывода комбинационного элемента, с него может поступать сигнал одновременно на входы нескольких элементов.
Количество элементов, для которых данный провод предоставляет входные данные, называется его коэффициентом ветвления (1ап-ош). Если к проводу не подсоединены выходы никаких элементов, он называется входом схемы (спсвй шрш), получающем входные данные из внешних источников. Если к проводу не подсоединен вход ни одного элемента, он называется выходом схемы (спсшг он1рщ), по которому выдаются результаты работы схемы. (Ответвление внутреннего провода также может выступать в роли выхода.) Чтобы определить задачу о выполнимости схемы, следует ограничиться рассмотрением схем с одним выходом, хотя на практике при разработке аппаратного оборудования встречаются логические комбинационные схемы с несколькими выводами.
Логическая комбинационная схема не содержит циклов. Поясним это нагляднее. Предположим, что схеме сопоставляется ориентированный граф С = (У, Е) с вершинами в каждом комбинационном элементе и к ориентированными ребрами для каждого провода, коэффициент разветвления которых равен к.
Ориентированное ребро (и, о) в этом графе существует, если провод соединяет выход элемента и со входом элемента о. Полученный в результате такого построения граф должен быть ациклическим. Часть Ч11. Избранные темы 1112 Рис. 34.8. Два экземпляра задачи о выполнимости схем Будем рассматривать наборы значений булевых переменных, соответствующих входам схемы (ггшЬ азз18пшеш). Говорят, что логическая комбинационная схема выполнима (зайзйаЫе), если она обладает выполняющим набором (зайзГу(пй азз18птеп1): набором значений, в результате подачи которого на вход схемы ее выходное значение равно 1.
Например, для схемы, изображенной на рис. 34.8а, выполняющий набор имеет вид (хз — — 1, хз = 1, хз = О); следовательно, эта схема выполнима. В упражнении 34.3-1 предлагается показать, что никакое присваивание значений величинам хм хз и хз не приведет к тому, что на выходе схемы, изображенной на рис. 34.8б, появится значение 1. Эта схема всегда выдает значение О, поэтому она невыполнима.
Задача о вынолнимости схемы (с1гсш1-за11збаЫ111у ргоЫет) формулируется так: выполнима ли заданная логическая юмбинационная схема, состоящая нз вентилей И, ИЛИ и НЕ. Однако чтобы поставить этот вопрос формально, необходимо принять соглашение по поводу стандартного кода для таких схем. Размер (з1хе) логической комбинационной схемы определяется как сумма юличества логических комбинационных элементов и числа проводов в схеме. Можно предложить код, использующийся при представлении графов, который отображает каждую заданную схему С на бинарную строку (С), длина которой выражается не более чем полиномиальной функцией от размера схемы.
Таким образом, можно определить формальный язык С1кс01т БАт = ((С): С вЂ” выполнимая схема) . Задача о выполнимости схем возникает при оптимизации компьютерного аппаратного обеспечения. Если какая-то подсхема рассматриваемой схемы всегда выдает значение О, то ее можно заменить более простой подсхемой, в юторой опускаются все логические вентили, а на выход подается постоянное значение О. Было бы полезно иметь алгоритм решения этой задачи, время которого выражалось бы полиномиальной функцией.
Глава 34. МР-полнота 1113 Чтобы проверить, разрешима ли данная схема С, можно попытаться просто перебрать все возможные комбинации входных значений. К сожалению, если в схеме )с входов, то количество таких комбинаций равно 2". Если размер схемы С выражается полиномиальной функцией от (с, то проверка всех комбинаций занимает время Й (2~), а эта функция по скорости роста превосходит полиномиальную функциют.
Как уже упоминалось, существует веский аргумент в пользу того, что не существует алгоритмов с полиномиальным временем работы, способных решить задачу о выполнимости схем, так как эта задача является ХР-полной. Разобьем доказательство ИР-полноты этой задачи на две части, соответствующие двум частям определения ХР-полнотьь Лемма 34.5. Задача о выполнимости схем принадлежит классу ХР. Доказаигевьсигво. В этом доказательстве будет сформулирован алгоритм А с двумя входными параметрами и полиномиальным временем работы, способный проверять решение задачи С~ксглт БАт.
В роли одного из входных параметров алгоритма А выступает логическая комбинационная схема С (точнее, ее стандартный код). Вторым входным параметром является сертификат, который представляет собой булевы значения на всех проводах схемы. (Существование сертификата меньшего объема предлагается показать в упражнении 34.3-4.) Алгоритм А строится следующим образом. Для каждого логического вентиля схемы проверяется, что предоставляемое сертификатом значение на выходном проводе правильно вычисляется как функция значений на входных проводах. Далее, если на выход всей цепи подается значение 1, алгоритм тоже выдает значение 1, поскольку величины, поступившие на вход схемы С, являются выполняющим набором.
В противном случае алгоритм выводит значение О. Для любой выполнимой схемы С, выступающей в роли входного параметра алгоритма А, существует сертификат, длина которого выражается полиномиальной функцией от размера схемы С, и который приводит к тому, что на выход алгоритма А подается значение 1. Для любой невыполнимой схемы, выступающей в роли входного параметра алгоритма А, никакой сертификат не может заставить этот алгоритм поверить в то, что эта схема выполнима. Алгоритм А выполняется в течение полиномиального времени: при хорошей реализации достаточно будет линейного времени. Таким образом, задачу С1ко.лт Блт можно проверить за полиномиальное время, и С1кОдт ЯАт е )т(Р.
И С другой стороны, сали размер схемы С равен 9 (2 ), то алгоритм со временем работы О (2") завершается по истечении времени, выражающегося полиномиальной функцией от размера схемы. Даже если Р ф ХР, эта ситуация не противоречит ХР-полноте задачи; из наличия алгоритма с полиномиальным временем работы лля особого случая не слелуег, что такой алгоритм существует во всех случаях. Часть Ч!1. Избранные темы 1114 Вторая часть доказательства ХР-полноты задачи С|всат Блт заключается в том, чтобы показать, что ее язык является НР-сложным.
Другими словами, необходимо показать, что каждый язык класса ХР приводится в течение полиномиального времени к языку Сщсий' Блт. Само доказательство этого факта содержит много технических сложностей, поэтому здесь приводится набросок доказательства, основанный на некоторых принципах работы аппаратного обеспечения компьютера.
Компьютерная программа хранится в памяти компьютера в виде последовательности инструкций. Типичная инструкция содержит код операции, которую нужно выполнить, адреса операндов в памяти и адрес, куда следует поместить результат. Специальная ячейка памяти под названием счетчик камалд (ргойгат соишег, РС) следит за тем, какая инструкция должна выполняться следующей.
При извлечении очередной инструкции показание счетчика команд автоматически увеличивается на единицу. Это приводит к последовательному выполнению инструкций компьютером. Однако в результате выполнения некоторых инструкций в счетчик команд может быть записано некоторое значение, что приводит к изменению обычного последовательного порядка выполнения. Таким образом организуются циклы и условные ветвления. В любой момент выполнения программы состояние вычислений в целом можно представить содержимым памяти компьютера.
(Имеется в виду область памяти, состоящая из самой программы, счетчика команд, рабочей области и всех других битов состояния, с помощью которых компьютер ведет учет выполнения программы.) Назовем любое отдельное состояние памяти компьютера конфигурацией (сопйкиапоп). Выполнение команд можно рассматривать как отображение одной конфигурации на другую. Важно то, что аппаратное обеспечение, осуществляющее это отображение, можно реализовать в виде логической комбинационной схемы, которая при доказательстве приведенной ниже леммы будет обозначена через М. Лемма 34.6. Задача о выполнимости схем является ХР-сложной. Доказаиельсемв.
Пусть Ь вЂ” язык класса ХР. Опишем алгоритм Г с полиномиальным временем работы, вычисляющий функцию приведения г", которая отображает каждую бинарную строку х на схему С = 1 (х), такую что з Е Ь тогда и только тогда, когда С е С~кс~дт БАт. Поскольку Ь е ХР, должен существовать алгоритм А, верифицирующий язык Ь в течение полиномиального времени. В алгоритме Г, который будет построен ниже, для вычисления функции приведения 1 будет использован алгоритм А с двумя входными параметрами. Пусть Т(п) — время работы алгоритма А в наихудшем случае для входной строки длиной и, а й > 1 — константа, такая что Т (п) = О (п~), и длина Глава 34.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
