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