Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 231
Текст из файла (страница 231)
МР-полнота 1115 сертификата равна О (и"). (В действительности время работы алгоритма А выражается полиномиальной функцией от полного объема входных данных, в состав которых входит и входная строка, и сертификат, но так как длина сертификата полиномиальным образом зависит от длины и входной строки, время работы алгоритма полиномиально зависит от и.) Основная идея доказательства заключается в том, чтобы представить выполнение алгоритма А в виде последовательности конфигураций.
Как видно из рис. 34.9, каждую конфигурацию можно разбить на следующие части: программа алгоритма А, счетчик команд РС, регистры процессора, входные данные х, сертификат у и рабочая память. Начиная с исходной конфигурации со, каждая конфигурация с; с помощью комбинационной схемы М, аппаратно реализованной в компьютере, отображается на последующую конфигурацию с,+~.
Выходное значение алгоритма А (О или 1) по завершении выполнения алгоритма А записывается в некоторую специально предназначенную для этого ячейку рабочего пространства. При этом предполагается, что после останова алгоритма А это значение не изменяется. Таким образом, если выполнение алгоритма состоит не более чем из Т (и) шагов, результат его работы хранится в определенном бите в ст1„). Алгоритм приведения Г конструирует единую комбинационную схему, вычисляющую все конфигурации, которые получаются из заданной входной конфигурации. Идея заключается в том, чтобы "склеить" вместе все Т (и) копий схемы М.
Выходные данные 1-й схемы, выдающей конфигурацию с;, подаются непосредственно на вход (г+ 1)-й схемы. Таким образом, эти конфигурации вместо того, чтобы в конце своей работы заносить выходное значение в один из регистров состояния, просто передают его по проводам, соединяющим копии схемы М. Теперь вспомним, что должен делать алгоритм приведения Е, время работы которого выражается полиномиальной функцией. Для заданных входных данных х он должен вычислить схему С = г' (х), которая была бы выполнима тогда и только тогда, когда существует сертификат у, удовлетворяющий равенству А (х, у) = 1. Когда алгоритм Г получает входное значение х, он сначала вычисляет и = ~х~ и конструирует комбинационную схему С', состоящую из Т (и) копий схемы М.
На вход схемы С' подается начальная конфигурация, соответствующая вычислению А (х, у), а выходом этой схемы является конфигурация ст1„). Схема С = г' (х), которую создает алгоритм Г, получается путем небольшой модификации схемы С'. Во-первых, входы схемы С', соответствующие программе алгоритма А, начальному значению счетчика команд, входной величине х и начальному состоянию памяти, соединяются проводами непосредственно с этими известными величинами. Таким образом, оставшиеся входы схемы соответствуют сертификату у.
Во-вторых, игнорируются все выходы схемы за исключением одного бита конфигурации сг(„), соответствующего выходному значению алгоритма А. Сконструированная таким образом схема С для любого входного параметра у Часть Ч11. Избранные темы 1116 с, т .,;: А; ..; ~ РС 1 ьгсптстоь~прсасссора ~ х 1сху с 1'Рабояаяа~амять яу. сс ~-,...,".',А:,',с.;1, РС 1::,:РсьвстгалролсссоРа~ . х. ~ у.'.'-~ Работая осиять с я„,, Г. с: .4'- с.',,--'Д РС,.РссстрыогоысЬррс~ х ~,. у„;-,~ Раоф: оьоять О,'~ сысоя Рис. 34.9.
Последовательность конфигураций, полученных в ходе работы алгоритма А, иа вход которого поступила строка х и сертификат у длиной 0 (и") вычисляет величину С (у) = А (к, у). Алгоритм приведения Г, на вход которого подается строка х, вычисляет описанную выше схему С и выдает ее. Осталось доказать два свойства. Во-первых, необходимо показать, что алгоритм Г правильно вычисляет функцию приведения у.
Другими словами, необходимо показать, что схема С выполнима тогда и толью тогда, когда существует сертификат у, такой что А (я, у) = 1. Во-вторых, необходимо показать, что работа алгоритма г' завершается по истечении полиномиального времени. Чтобы показать, что алгоритм г корректно вычисляет функцию приведения, предположим, что существует сертификат р длиной 0 (пь), таюй что А (:т, у) = = 1.
Тогда при подаче битов сертификата у на вход схемы С на выходе этой схемы получим значение С (у) = А (х, у) = 1. Таким образом, если сертификат Глава 34. ИР-полнота 1117 существует, то схема С выполнима. С другой стороны, предположим, что схема С выполнима. Тогда существует такое входное значение у, что С (у) = 1, откуда можно заключить, что А (т, у) = 1. Итак, алгоритм Г корректно вычисляет функцию приведения.
Чтобы завершить набросок доказательства, осталось лишь показать, что время работы алгоритма Е выражается полиномиальной функцией от п = ~х~. Первое наблюдение, которое можно сделать, заключается в том, что количество битов, необходимое для представления конфигурации, полиномиально зависит от п. Объем программы самого алгоритма А фиксирован и не зависит от длины его входного параметра х.
Длина входного параметра х равна и, а длина сертификата у— О (пь). Поскольку работа алгоритма состоит не более чем из О (пь) шагов„объем необходимой ему рабочей памяти также выражается полиномиальной функцией от п. (Предполагается, что эта область памяти непрерывна; в упражнении 34.3-5 предлагается обобщить доказательство для случая„ когда ячейки, к которым обращается алгоритм А, разбросаны по памяти большего объема, причем разброс ячеек имеет свой вид для каждого входного параметра к.) Размер комбинационной схемы М, реализованной аппаратной частью компьютера, выражается полиномиальной функцией от длины конфигурации, которая в свою очередь является полиномиальной от величины О (п") и, следовательно, полиномиально зависит от и.
(В большей части такой схемы реализуется логика системы памяти.) Схема С состоит не более чем из 1 = О (и") копий М, поэтому ее размер полиномиально зависит от и. Схему С для входного параметра х можно составить в течение полиномиального времени при помощи алгоритма приведения К, поскольку каждый этап построения длится в течение полиномиального времени. Таким образом, язык С~нолт БАт не проще любого языка класса ХР, а поскольку он относится к классу ХР, он является ХР-полным.
Теорема 34.7. Задача о выполнимости схем является ИР-полной. Доказатеиьсюиво. Справедливость теоремы непосредственно следует из лемм 34.5 и 34.6, а также из определения ХР-полноты. М Упражнения 34.3-1. Убедитесь, что схема, изображенная на рис. 34.86, невыполнима. 34.3-2. Покажите, что отношение <р является транзитивным в отношении языков; другими словами, покажите, что из Е1 <р Ьз и Ьз <р Ьз следует г1 <г ~з 34.3-3.
Докажите, что Е <р Т тогда и только тогда, когда А <р Ь. Часть Чй. Избранные темы 1118 34.3-4. Покажите, что в качестве сертификата в альтернативном доказательстве леммы 34.5 можно использовать выполняющий набор. С каким сертификатом легче провести доказательство? 34.3-5. В доказательстве леммы 34.6 предполагается, что рабочая память алгоритма А занимает непрерывную область полиномиального объема.
В каком месте доказательства используется это предположение? Покажите, что оно не приводит к потере общности. 34.3-6. Язык Б называется полным (сошр1е~е) в классе языков С относительно приведения в течение полиномиального времени, если Ь е С и Ь' <р Ь для всех Ь' Е С. Покажите, что множества 9 и (О, 1)' — единственные языки класса Р, которые не являются полными в этом классе относительно приведения за полиномиальное время. 34.3-7. Покажите, что язык Ь полный для класса ХР тогда и только тогда, когда язык Е полный для класса со-ХР.
34.3-8. Алгоритм приведения Г в доказательстве леммы 34.6 строит схему С = = 7" 1х) на основе знаний о х, А и 1с. Профессор заметил, что алгоритм Р получает в качестве аргумента только х. В то же время об алгоритме А и константе к, с помощью которой выражается его время работы О (пь), известно лишь то, что они существуют (поскольку язык Б принадлежит к классу ХР), но не сами их значения. Из этого профессор делает вывод, что алгоритм г' может не построить схему С и что язык С~ксглт БАт не обязательно ХР-сложный.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
