Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 251
Текст из файла (страница 251)
Зв исключением сергифнюта р, исходная конфигурация са явтегся константной. Булева комбинаторная схема М отабрюкает каждую конфигурацию на ачерелную. Выхсц представляет собой некоторый предопределенный бит в рабочей памяти. рис. 34.9, каждую конфигурацию можно разбить на следуклцие части: программа алгоритма А, счетчик команд РС, регистры процессора, входные данные х, сертификат р и рабочая память. Начиная с исходной конфигурации са, каждая конфигурация с; с помощью комбинационной схемы М, аппаратно реализованной в компьютере, отображается на следующую за ней конфигурацию с;+!. Выходное значение алгоритма А (О нли 1) по завершении выполнения алгоритма А записывается в некоторую специально предназначенную для этого ячейку рабочей памяти.
При этом предполагается, что после останова алгоритма А это значение не изменяется. Таким образом, если выполненно алгоритма состоит не более чем нз Т(п) шагов, результат его работы хранится в определенном бите в ог!„р Алгоритм приведения г конструирует единую комбинационную схему, вычисляющую все конфигурации, которые получаются из заданной входной конфигурации. Идея заключается в том, чтобы "склеить" вместе все Т(п) копий схемы М. Выходные данные 1-й схемы, выдающей конфигурацию сн подаются непосредственно на вход (1+ 1)-й схемы. Таким образом, эти конфигурации вместо того, чтобы храниться в памяти компьютера, просто передаются по проводам, соединяющим копии схемы М.
Теперь вспомним, что должен делать алгоритм приведения Е, время работы которого выражается полиномиальной функцией. Для заданных входных данных х он должен вычислить схему С = 5(х), которая была бы выполнима тогда и только тогда, когда существует сертификат у, такой, что А(х, у) = 1.
Когда алгоритм Г получает входное значение к, он сначала вычисляет и = ~х~ и конструирует комбинационную схему С', состоящую из Т(п) копий схемы М. На вход схемы С' подается начальная конфигурация, соответствующая вычислению А(х, у), а выходом этой схемы является конфигурация сг(„1. Схема С = 5(х), которую создает алгоритм Г, получается путем небольшой модификации схемы С'. Во-первых, входы схемы С', соответствующие программе алгоритма А, начальному значению счетчика команд, входной величине х и начальному состоянию памяти, соединяются проводами непосредственно с этими известными величинами.
Таким образом, оставшиеся входы схемы соответствуют сертификату у. Во-вторых, игнорируются все выходы схемы, за исключением одного бита конфигурации сг(,Ч, соответствующего выходному значению алгоритма А. Сконструированная таким образом схема С для любого входного параметра у длиной 0(пь) вычисляет величину С(у) = А(х, у). Алгоритм приведения Г, на вход которого подается строка х, вычисляет описанную выше схему С и вьщает ее. Докажем два свойства.
Во-первых, покажем, что алгоритм Е правильно вычисляет функцию приведения 5, т.е. что схема С выполнима тогда и толью тогда, когда существует сертификат у, такой, что А(х, у) = 1. Во-вторых, покажем, что работа алгоритма Е завершается за полиномиальное время. Чтобы показать, что алгоритм Е корректно вычисляет функцию приведения, предположим, что существует сертификат у длиной 0(пь), такой, что А(х, у) = 1.
Тогда при подаче битов сертификата у на вход схемы С на выходе этой схемы получим значение С(у) = А(х, у) = 1. Таким образом, если сертификат существует, то схема С выполнима. Для доказательства в обратном направлении предположим, что схема С выполнима. Тогда существует такое входное значение у, что С(у) = 1, откуда можно заключить, что А(х, у) = 1. Итак, алгоритм Г корректно вычисляет функцию приведения. Чтобы завершить набросок доказательства, осталось лишь показать, что время работы алгоритма Е выражается полиномиальиой функцией от и = ~х~. Первое наблюдение, которое можно сделать, заключается в том, что количество битов, необходимое для представления конфигурации, полиномиально зависит от и.
Объем программы самого алгоритма А фиксирован и не зависит от длины его входного параметра х. Длина входного параметра х равна и, а длина сертификата у — 0(нь). Поскольку работа алгоритма состоит не более чем из 0(пь) ша- !!26 Часть рц. Избранные темы гов, объем необходимой ему рабочей памяти также выражается полиномиальной функцией от и. (Предполагается, что эта область памяти непрерывна; в упр.
34.3.5 предлагается обобщить доказательство для случая, когда ячейки, к которым обращается алгоритм А, разбросаны по памяти большего объема, причем разброс ячеек имеет свой вид для каждого входного параметра х.) Размер комбинационной схемы М, реализующей аппаратную часть иэмпьютера, выражается полиномиальной функцией от длины конфигурации, которая, в свою очередь, является полиномиальной от величины 0(п~) и, следовательно, полиномиально зависит от и. (В большей части такой схемы реализуется логика системы памяти.) Схема С состоит не более чем из ! = 0(п") копий М, поэтому ее размер полиномиально зависит от и.
Схему С для входного параметра х можно составить в течение полиномиального времени с помощью алгоритма приведения Г, поскольку каждый этап построения длится в течение полиномиапьного времени. Таким образом, язык С1РсСП1Т-БАТ не проще любого языка класса ХР, а поскольку он относится к классу ХР, он является ХР-полным. Теорема 34. 7 Задача о выполнимости схем является Хр-полной. Доказаязельсязео. Справедливость теоремы непосредственно следует из лемм 34.5 и 34.6, а также из определения ХР-полноты. Упражнения 34.3.! Убедитесь, что схема, изображенная на рис.
34.8,(б), невыполнима. 34.3.2 Покажите, что отношение <р является транзитивным в отношении языков; дру- ГНМИ СЛОВаМИ, ПОКажИтЕ, ЧтО ИЗ з 1 <Р ЬЗ И ЬЗ <Р ЛЗ СЛЕДУЕТ Ьз <Р ЬЗ. 34.3.3 Докажите, что Е <р 1 тогда и только тогда, когда з' <р Е. 34.3.4 Покажите, что в качестве сертификата в альтернативном доказательстве леммы 34.5 можно использовать выполняющий набор.
С каким сертификатом легче провести доказательство? 34.3.5 В доказательстве леммы 34.6 предполагается, что рабочая память алгоритма А занимает непрерывную область полиномиального обьема. В каком месте доказательства используется это предположение? Покажите, что оно не приводит к потере общности. Глава 14. УР-полнота 34.3.6 Язык Ь называется полным (сошр!е1е) в классе языков С относительно приведения за полииомиальиое время, если Ь Е С и 1.' <р Ь для всех Ь' Е С.
Покажите, что множества 9 и (О, 1)' — единственные языки класса Р, которые ие являются полными в этом классе относительно приведения за полииомиальиое время. 34.3. 7 Покажите, что по отношению к приведениям за полииомиальиое время (см. упр, 34,3.6) 1 является полным в классе ХР тогда и толью тогда, югда Х является полным в со-ХР. 34.3.8 Алгоритм приведения Р в доказательстве леммы 34.6 строит схему С = У(х) иа основе знаний о я, А и к. Профессор заметил, что алгоритм Г получает в качестве аргумента только х.
В то же время об алгоритме А и константе к, с помощью которой выражается его время работы 0(п"), известно лишь то, что оии существуют (поскольку язык Ь принадлежит к классу ХР), ио ие сами их значения. Из этого профессор делает вывод, что алгоритм Р может ие суметь построить схему С и что язык С1НСШТ-ЯАТ ие обязательно ХР-сложиый. Объясните, какая ошибка содержится в рассуждеииях профессора.
34.4. Доказательства ХР-полпоты ХР-полиота для задачи о выполнимости схем основана иа непосредственном доказательстве соотношения Ь <р С1КС1)1Т-ЕАТ для каждого языка Ь Е ХР. В этом разделе будет показано, как доказать ХР-полиоту языка без непосредственного приведеиия каясдого языка из класса ХР к заданному языку. Мы проиллюстрируем эту методику, доказав ХР-полиоту различных задач иа выполнимость формул. Намного большее юличество примеров применения этой методики содержится в разделе 34.5.
Основой рассматриваемого в этом разделе метода, позволяющего доказать ХР- полноту задачи, служит сформулированная ниже лемма. Лемма 34.8 Если язык Е такой, что Ь' <р Ь для некоторого Ь' е ХРС, то Ь является ХР- сложным. Если, кроме того, Ь Е ХР, то Ь Е ХРС. Доказательство. Поскольку язык 1.' ХР-полный, для всех 1н Е ХР мы имеем Ьн <р Ь'.
Согласно предположению 1' <р Ь, Таким образом, из траизитивиости (упр. 34.3.2) имеем Ьн <р Ь, что показывает, что задача Ь ХР-сложиая. Если Ь Е ХР, кроме того, 1 Е ХРС. Другими словами, если язык 1.', о котором известно, что ои — Хр-полный, удается свести к языку Ь, тем самым к этому языку неявно сводится любой язык !/28 Часть Р11. ИэГранные тены класса ХР. Таким образом, лемма 34.8 предоставляет метод доказательства ХР- полноты языка Ь, состояший из перечисленных ниже этапов. 1. Доказывается, что Б Е ХР.
2. Выбирается язык Ь', о котором известно, что он ХР-полный. 3. Описывается алгоритм, который вычисляет функцию 1, отображающую каждый экземпляр х 6 (О, 1)* языка Ь' на экземпляр Г" (х) языка Ь. 4. Доказывается, что для функции 1 соотношение х б Ы выполняется тогда и только тогда, когда 3(х) Е Ь для всех х Е (О, 1) . 5. Доказывается, что время работы алгоритма, вычисляюшего функцию г", полиномиальное. (На шагах 2 — 5 доказывается ХР-сложность языка Б.) Эта методология приведения с помощью одного языка, для которого известно, что он Хр-полный, намного проше, чем процесс, когда непосредственно демонстрируется, как выполнить приведение для каждого языка из класса ХР. Доказательство соотношения С1КСШТ-БАТ Е ХРС вЂ” первый важный шаг в этом направлении.
Знание того факта, что задача о выполнимости схемы является ХР-полной, позволяет доказывать ХР-полноту других задач намного проще. Более того, по мере расширения списка известных ХР-полных задач появляется все больше возможностей для выбора языков, которые будут использоваться для приведения. Выполнимость формулы Проиллюстрируем методику приведения, доказав ХР-полноту задачи определения, выполнима ли не схема, а формула. Именно для этой задачи впервые была доказана ХР-полнота. Сформулируем задачу о яыяалоимосяэи формулы ((оппп!а заг(зйэаЬ1111у) в терминах языка ЯАТ.
Экземпляр языка ЯАТ вЂ” это булева формула ф, состоящая из перечисленных ниже элементов. 1. и булевых переменных: хмхз,...,х„. 2. т булевых соединяющих элементов, в роли которых выступает произвольная логическая функция с одним или двумя входными значениями и одним выходным значением, например гэ (И), и (ИЛИ), (НЕ), — ~ (имплнкация), +~ (эквивалентность). 3. Скобки. (Без потери общности предполагается, что лишние скобки не употребляются, т.е. что на каждый логический соединяюшнй элемент приходится не более одной пары скобок.) Логическую формулу б легко закодировать строкой, длина которой выражается полиномиальной функцией от п+т. Как и для логических комбинационных схем, наборехы значений (Птн)э азз18пэпеп1) логической формулы ф называется множество значений переменных этой формулы, а выполняющим наборам (за!Ыу1пй азяйпшепэ) — такой набор значений, при котором результат вычисления формулы Глава л4.
ФР-лалиата 1!29 равен 1. Формула, для которой существует выполняющий набор, является выпал- иимой (заг(зйао)е). В задаче о выполнимости спрашивается, выполнима ли данная формула. В терминах формальных языков эта задача имеет вид ЯАТ = ((ф): ф — выполнимая булева формула) В качестве примера приведем формулу ф = ((хг -+ х2) Ч (( ~хг +> хз)Ч х4)) Л х2 у жпорой имеется выполняющий набор (х1 = О, хз = О, хз = 1, х4 = 1), по- скольку ф=((0 — ~0)Ч ((-04+1)Ч1))Л 0 = (1 Ч .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
