Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 250
Текст из файла (страница 250)
Таким образом, эта схема невыполнима. элемента и со входом элемента и. Полученный в результате такого построения граф должен быль ациклическим. Будем рассматривать наборы значений (Ппбз азгййшпепт) булевых переменных, соответствующих входам схемы. Говорят, что логическая комбинационная схема выполнима (эайзбаЫе), если она имеет вынолняюи(ий набор (вабзГу(пй ааз(8пшепт): набор значений, в результате подачи которого на вход схемы ее выходное значение равно 1.
Например, для схемы, изображенной на рис. 34.8,(а), выполшпощий набор имеет вид (хз = 1, хз = 1, хз = О); следовательно, эта схема выполнима. В упр. 34.3.1 предлагается показать, что никакое присваивание значений величинам хт, хз и хз не приведет к значению 1 на выходе схемы, изображенной на рис. 34.8,(б). Эта схема всегда выдает значение О, поэтому она невыполнима.
Задача о выпачнимости схемы (с(тсшт-аа1(збаЬ111)у ргоЫещ) формулируется следующим образом: выполнима ли заданная логическая комбинационная схема, состоящая из элементов И, ИЛИ и НЕ. Однако, чтобы поставить этот вопрос формально, необходимо принять соглашение по поводу стандартного кода для таких схем. Размер (з(ге) логической комбинационной схемы определяется как сумма количества логических комбинационных элементов и числа проводов в схеме. Можно предложить код, используемый при представлении графов, который отображает каждую заданную схему С на бинарную строку (С), длина которой выражается не более чем полиномиальной функцией от размера схемы. Таким обраюм, можно определить формальный язык С1ИС(ЛТ-ЯАТ = ((С): С является выполнимой булевой схемой) Задача о выполнимости схем возникает при оптимизации компьютерного аппаратного обеспечения.
Если какая-то подсхема рассматриваемой схемы всегда выдает значение О, то ее можно заменить более простой подсхемой, в которой опускаются все логические элементы, а на выход подается постоянное значение О. Было бы полезно иметь алгоритм решения этой задачи, время жзгорого выражалось бы полиномиальной функцией. И22 Часть Р)й Избранные темы Чтобы проверить, разрешима лн данная схема С, можно попытаться просто перебрать все возможные комбинации входных значений. К сожалению, если в схеме )с входов, то количество таких комбинаций равно 2ь.
Если размер схемы С выражается полнномнальной функцией от )с, то проверка всех комбннацнй заннмает время Й(2ь), а эта функция по скоростн роста превосходит полнномнапьную функцнюй. Как уже упоминалось, имеется веский аргумент в пользу того, что не существует алгоритмов с полнномнальным временем работы, способных решить задачу о выполнимости схем, так как эта задача является ХР-полной. Разобьем доказательство ХР-полноты этой задачи на две части, соответствующие двум частям определения ХР-полнотьь Лемма 34.5 Задача о выполнимости схем принадлежит классу ХР.
Доказательство. В этом доказательстве будет сформулирован алгоритм А с двумя входными параметрами н полнномнальным временем работы, способный проверять решение задачи С1КСШТ-ЯАТ. В роли одною нз входных параметров алгоритма А выступает логическая комбннацнонная схема С (точнее, ее стандартный код). Вторым входным параметром является сертификат, который представляет собой булевы значения в проводах схемы. (См, другой сертификат, меньшего объема, в упр.
34.3.4.) Алгоритм А строится следующим образом. Для каждого логического элемента схемы проверяется, что предоставляемое сертификатом значение на выходном проводе правильно вычисляется как функция значений на входных проводах. Далее, если на выход всей цепи подается значение 1, алгоритм также выдает значенне 1, поскольку величины, поступившие на вход схемы С, являются выполняющнм набором.
В противном случае алгоритм выводит значение О. Для любой выполнимой схемы С, выступающей в роли входного параметра апгорнтма А, существует сертификат, длина которого выражается полнномнальной функцией от размера схемы С, н который приводит к тому, что на выход алгоритма А подается значение 1. Для любой невыполнимой схемы, выступающей в роли входного параметра алгоритма А, никакой сертификат не может заставить этот алгоритм поверить в то, что эта схема выполнима.
Алгоритм А выполняется за полнномнальное время: прн хорошей реапнзацнн достаточно будет линейного времени. Таким образом, задачу С1КС(ДТ-ЯАТ можно проверить за полнномнапьное время, н С1КС(ЛТ-ЯАТ е ХР. Вторая часть доказательства МР-полноты задачи С1КСШТ-БАТ заключается в том, чтобы показать, что ее язык является ХР-сложным. Другими словами, необходимо показать, что каждый язык класса ХР приводится за полнномнапьное вС другой стропы, если размер схемы С равен сз(2" ), то алтарное со временем работы О (2" ) завершается по истечении времен», выражаемото полиномиальной функцией от размера схемы. Даже есл» Р ,-Е ХР, зта ситуация не противоречит )ЧР-полноте задачи; из наличия алгоритма с полиномиальимм временем работы лля частного случая ие следует, что такой ттрити сушествует в общем случае.
Глава 34. МР-аавната время к языку С1ВС1ЛТ-ЯАТ. Само доказательство этого факта содержит много технических сложностей, поэтому здесь приводится набросок доказательства, основанный на некоторых принципах работы аппаратного обеспечения компьютера. Компьютерная программа хранится в памяти компьютера в виде последовательности инструкций. Типичная инструкция содержит код операции, которую нужно выполнить, адреса операндов в памяти и адрес, куда следует поместить результат. Специальная ячейка памяти под названием счетчик каяванд (ргойгаш сошпег — РС) следит за тем, какая инструкция должна выполняться следующей. При извлечении очередной инструкции показание счетчика команд автоматически увеличивается на единицу. Это приводит к последовательному выполнению инструкций компьютером.
Однако в результате выполнения определенных инструкций в счетчик команд может быть записано некоторое значение, что приводит к изменению обычного последовательного порядка выполнения. Таким образом организуются циклы н условные ветвления. В любой момент выполнения программы состояние вычислений в целом можно представить содержимым памяти компьютера. (Имеется в виду область памяти, состоящая из самой программы, счетчика команд, рабочей области и всех других битов состояния, с помощью которых компьютер ведет учет выполнения программы.) Назовем любое отдельное состояние памяти компьютера конфи;рраг4ией (сопййшабоп). Выполнение команд можно рассматривать как отображение одной конфигурации на другую. Важно то, что аппаратное обеспечение, осуществляющее это отображение, можно реализовать в виде логической комбинационной схемы, которая при доказательстве приведенной ниже леммы будет обозначена как М.
Лемма 34.6 Задана о выполнимости схем является Хр-сложной. Докизалвельслвао. Пусть 1, — язык класса гчР. Опишем алгоритм г' с полиномиальным временем работы, вычисляющий функцию приведения 1, которая отображает каждую бинарную строку х на схему С = )'(х), такую, что х е Ь тогда и только тогда, когда С е С1НС)ЛТ-ЯАТ. Поскольку Е Е ИР, должен существовать алгоритм А, верифицирукнций язык Ь за полиномиальное время. В алгоритме Е, который будет построен ниже, для вычисления функции приведения )' будет использован алгоритм А с двумя входными параметрами. Пусть Т(п) — время работы алгоритма А в наихудшем случае для входной строки длиной п, й > 1 — константа, такая, что Т(п) = 0(п"), а длина сертификата равна 0(п").
(В действительности время работы алгоритма А выражается полиномиальной функцией от полного объема входных данных, в состав которых входят и входная строка„и сертификат, но так как длина сертификата полиномиальным образом зависит от длины п входной строки, время работы алгоритма полиномиально зависит от и.) Основная идея доказательства заключается в том, чтобы представить выполнение алгоритма А в виде последовательности конфигураций.
Как видно из Часть !7ь Набранные темы са 1-,,:"!",:,:.;:а!;.::::;,:"Т- Р~"-~3йхийригф~~~~у~~,г,х.'. ~!:,:":;:~~':,.',! Рабачачйнцкгн1 сг ~:; -:; А: -: РС !Рипа~Игрец!Ксо!ы, х' Г:,Эт-:„:ьрабоьтягиьыть1 '„-,~ ....хлх З =,с' .. о. с ::: дг':.:' -".;'::,-~ спм ~::,,:.: 'Ад;..""~ Рь". !РфФу~рриввжарв~ .";:,у'::-'1 Рвб:,:~тая!~~ ~ О/! инхад Рис. 34.9. Последовательность конфигураций, полученных в ходе работы аюорипча А, на вжю которого поступили строка х и сертификат р. Каждая жтфигурашгя представляет состояние компьютера для одного шага вычислений и, помимо А, х и у, включает счетчик команд (РС), регистры процессора и рабочую пашнь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
