Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений, страница 112

ПРОБЛЕМЫ, РАЗРЕШИМЫЕ В ПОЛИНОМИАЛЬНОМ ПРОСТРАНСТВЕ 487 "Сердцем" доказательства является детерминированная рекурсивная проверка, может ли НМТ Аг перейти от МО 1 к МО./ не более, чем за т переходов. ДМТ /) систематически проверяет все промежуточные МО К, чтобы убедиться, может ли А' перейти от 1 к К за т/2 переходов, а затем перейти от К к.l за т/2 переходов. Итак, представим, что существует рекурсивная функция геас/г(1 .1, т), решающая, верно ли, что 1 )- ./ не более, чем за т/2 переходов. Рассмотрим ленту машины Р как магазин, в который помещаются аргументы рекурсивных вызовов функции геас/г, т.е. один элемент магазина хранит [1,./, т).

Алгоритм функции геас/г представлен на рис. 1! .3.~ ВООЕЕАН ЕВНСТ10)1 геасН11, 3, ж) 10: 1, 7! 1))Т: и/ ВЕС1Н 1Е 1аг == 1) ТНЕ)ч /* Оазис */ ВЕ61Н проверить, что 1 == 3 или 1 может стать Ю за 1 переход; если так, НЕТОН)) ТВОЕ, иначе НЕТОН)Ч ГАЕЯЕ! ЕНВ; ЕЕЯЕ /* индуктивная часть */ ВЕО1)) ГОН каждая возможная Р/О К ОО 1Е )геасй11, К,гс/2) АНО геасН(К, д,ж/2)) ТНЕН НЕТОНН ТВОЕ! НЕТОНН ЕАЕЯЕ; ЕНО; ЕНО! Рис. ! !.3.

Рекурсивная функния геасп проверяет, можно ли зо установленное число переходое перейти от одного МО к другому Важно заметить, что, хотя геас/г вызывает саму себя дважды, она делает это последовательно, поэтому в любой момент времени активен лишь один вызов. Таким образом, если начать с элемента магазина [1ь./ь т), то в любой момент времени существует только один вызов [1, /в т/2), один вызов [1в,/в т/4), еще один [1е ./о т/81 и так далее, пока в некоторой точке третий аргумент не станет равным 1. В этот момент геасй может применить базисный шаг и не нуждается в рекурсивных вызовах. Она проверяет, верно ли, что 1 )- /или1=/, и возвращает сгце, если это так, и Та1ве — если нет.

На рис. 114 представлен общий вид магазина ДМТ Р, когда существует столько активных вызовов геас/г, сколько возможно при начальном количестве переходов т. Рис. !!.4 Лента ДМТ, имитируюи!ей НМГс помои/ьюрекурснвных вызовов геас)з НΠ— МО ()нмапгапеоиз Оезспрноп — мгновенное описание). — Прим. перев. 488 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ Хотя может показаться, что возможно много вызовов функции геасЬ, и лента, изображенная на рис. 11.4, может стать очень длинной, мы докажем, что она не будет "слишком длинной", т.е., если начать с числа переходов л1, то в любой момент времени на ленте не может быть более !од т элементов магазина. Поскольку теорема 11.4 гарантирует, что ПМТ Ф не может совершить более с'ВЯ переходов, начальное значение ьч также не превышает сг'"'. Таким образом, число элементов магазина не превосходит 1одзс""', т.е.

О(р(л)), и у нас есть все необходимое для доказательства следующей теоремы. Теорема 11.5 (теорема Сэвича). РБ = МРБ. Доказательство. Очевидно, что РБ ~ Л~Ро, поскольку каждая ДМТ является также и НМТ. Таким образом, достаточно доказать, что ФР$ с Ро, т.е., если А допускается НМТ Ж с ограничением пространства р(п), где р(л) — полипом, то 1. также допускается ДМТ Е>, пространство которой ограничено другим полиномом фп).

В действительности будет показано, что д(п) можно выбрать равным по порядку квадрату р(л). По теореме 11.3 можно предполагать, что, если Аг допускает, то делает это в пределах с| М"' шагов, где с — некоторая константа. Получив вход и длиной л, )) исследует, что делает У со входом я, многократно помещая тройки вида (1,, /, т] на свою ленту и вызывая геас6 с этими аргументами. Здесь 4, является начальным МО машины Ж со входом и, 1 — некоторое допускающее МО, в котором используется не более р(л) клеток (различные.l систематически перечисляются машиной !У с помощью рабочей ленты),а и= с ""'. Выше было обосновано, что рекурсивных вызовов, активных одновременно, не может быть более !одз гл, т.е, один с аргументом и, один с аргументом гл/2, один с аргументом т/4 и так далее до 1.

Таким образом, существует не более!одз т элементов магазина, а !ойз пг есть 0(р(п)). Элементы магазина сами по себе занимают пространство 0(р(п)). Причина в том, что для записи каждого МО нужно 1 ьр(п) клеток, а для записи ш в двоичном виде— !оя,с~ х"~, т.е. 0(р(л)) клеток. Таким образом, полный элемент магазина, состоящий из двух МО и целого числа, занимает пространство 0(р(п)). Поскольку !) может иметь не более О(р(н)) элементов магазина, обшее количество используемого пространства составляет О(р~(л)). Это количество полиномиально, если р(п) — полипом, и мы делаем вывол, что Ь имеет ДМТ с полиномиально ограниченным пространством.

Р В заключение можно уточнить информацию о классах сложности, включая классы с полиномиально ограниченным пространством. Полная диаграмма представлена на рис. П.5. 11.3. Проблема, полная для РЯ В этом разделе представлена проблема, которая называется "булевы формулы с кван- торами", и показано, что она полна лля РЯ. 489 11.3. ПРОБЛЕМА, ПОЛНАЯ ДЛЯ РЯ Рис. 115.

Известные соотношения между классами языков 11.3.1. Рв-полнота Проблема Р определяется как полная для РЯ (РЯ-полная), если выполняются следуюшие условия. 1. Р принадлежит РЯ. 2. Все языки Е из РЯ полиномиально сводимы к Р. Отметим, что условия РЯ-полноты похожи на условия ХР-полноты — сведение должно выполняться за полиномиальное время. Это позволило бы установить, что Р = РЯ, если бы какая-нибудь РЯ-полная проблема оказалась в Р, и что ЛT= РЯ, если бы она оказалась в ЛР. Если бы сведения были лишь в полиномиальном пространстве, то размер выхода мог бы быть экспоненциальным относительно размера входа, и невозможно было бы прийти к заключению следующей теоремы. Но, ограничившись сведениями, полино- миальными по времени, получаем желаемые взаимосвязи.

Теорема 11.6. Пусть Р— РЯ-полная проблема. Тогда: а) если Р принадлежит Р, то )з = 'РЯ; б) если Р принадлежит ЛР, то Л"Р = 'РЯ. Доказательство. Докажем вариант а. Для любого Е из РЯ известно, что существует полиномиальное 1по времени) сведение Е к Р. Пусть оно занимает время фя). Предположим, Р принадлежит Р и имеет алгоритм с полиномиальным временем, например р(н). По данной цепочке зе, принадлежность которой языку Е мы хотим проверить, можно, используя сведение, получить цепочку х, находяшуюся в Р тогда и только тогда, когда зв 490 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ принадлежит Е. Поскольку сведение занимает время д(~зк)), цепочка х не может быть длиннее, чем су()н().

Принадлежность х языку Р можно проверить за время р(1к1), т.е. р(д()н()), полиномиальное относительно 1зк!. Приходим к выводу, что дпя Е существует полиномиальный алгоритм. Следовательно, каждый язык Е из РБ принадлежит Р. Поскольку включение Р в РЕ очевидно, приходим к выводу, что если Р принадлежит Р, то 'Р= РБ. Доказательство пункта б, где Р принадлежит Л"Р, аналогично и оставляется читателю. 11.3.2. Булевы формулы с кванторами Продемонстрируем проблему Р, полную для РЕ. Но сначала нужно изучить термины, в которых формулируется зта проблема, называемая "булевы формулы с кванторами*' (йпапбйед Ьоо!еап гогпш1ав), или КБФ. Грубо говоря, булева формула с кванторами — это булево выражение с добавлением операторов гГ ("для всех") и 3 ("существует'*), Выражение (Чх)(Е) означает, что Е истинно, если все вхождения х заменить 1 (истина), а также, если все вхождения х заменить О (ложь).

Выражение (Зх)(Е) означает, что Е истинно, если или все вхождения х заменить 1, или все вхождения х заменить О, или в обоих случаях. Для простоты описания предположим, что ни одна КБФ не содержит двух и более кваитификаний (1Г или Э) одной и той же переменной х. Это ограничение не является существенным, и соответствует, грубо говоря, запрещению того, чтобы две различные функции в программе использовали одну и ту же локальную переменную . Формально, 4 булевы формулы с кванторани (КБФ) определяются следующим образом.

1. О (ложь), 1 (истина) или любая переменная являются КБФ. 2. Если Е и г" — КБФ, то КБФ являются (Е), -(Е), (Е) л(г") и (Е) м (г), представляя Е в скобках, отрицание Е, логическое И Е и г" и логическое ИЛИ Е и Е, соответственно. Скобки можно опускать, если они избыточны, используя обычные правила приоритета (старшинства): НЕ, затем И, затем ИЛИ. Часто используется "арифметический*' стиль представления И и ИЛИ, когда И представлен непосредственным соседством (знак операции отсутствует), а ИЛИ вЂ” знаком ь. Таким образом, вместо (Е)л (г) часто используется (Е)(г), а вместо (Е) ч (г) — (Е) ь (г). 3.

Если Š— КБФ без квантификации переменной х, то (гГх)(Е) и (Эх)(Е) — КБФ. При этом говорят, что областью действия переменной х является выражение Е. Неформально говоря, х определена только в пределах Е, подобно тому, как областью дей- ' Два различных использования одного н того же имени переменной всегда можно переименовать, как в программах, так н в булевых формулах с квантарамн. В программах нег нужды избегать повторного использования одного н того же локального имени, но в КБФ удобно предполагать, что повторных использований нет. 491 11.3. ПРОБЛЕМА, ПОЛНАЯ ДЛЯ РБ ствия (определения) переменной в программе является функция, в которой эта пере- менная определена. Скобки вокруг Е (но не вокруг квантификации) можно удалить, если не возникает неоднозначности. Однако во избежание нагромождения вложен- ных скобок цепочка квантификаций вида (Чх)НЗу)((Чс)(Е))) а не с парой для каждой кван- (11.! ) записывается только с одной парой скобок вокруг Е тификации в цепочке, т.е, в виде (Чх)(Зу)(Чл)(Е).

Пример 11.7. Рассмотрим пример КБФ: (Чх)((Зу)(ху) ь (Чз)(- х е г)) Сначала переменные х ну связываются операцией И, затем применяется квантер (Чу) для получения подвыражения (Зу)(ху). Аналогично строится булево выражение хе к и применяется квантор (Чл) для получения подвыражения (Чх)( х + х). Далее эти выражения становятся операндами ИЛИ; скобки в выражении не нужны, поскольку + (ИЛИ) имеет минимальный приоритет. Наконец, к этому выражению применяется квантор (Чх) и получается вся указанная КБФ. Е) 11.3.3. Вычисление булевых формул с кванторами л выражения. Базис. Если длина выражения 1, то оно может быть только константой О или 1 (любая переменная была бы свободной).

Значением выражения является оно само. Индукция. Пусть дана КБФ длиной л >! без свободных переменных, и можно вычислить любое выражение меньшей длины, если в нем нет свободных переменных. Возможны б видов такой КБФ. 492 ГЛАВА 11. ДОПОЛНИТЕЛЬНЫЕ КЛАССЫ ПРОБЛЕМ Определим формально значение КБФ. Интуитивную идею для этого дает прочтение Ч как "для всех"„а 3 — как "существует". КБФ (11.1) утверждает, что для всех х (те. х = О или х =!) существует у, при котором как х, так ну истинны, или же для всех х истинно —.х + =. Это утверждение оказывается истинным. Если х = 1, то можно выбрать у = ! исделатьху истинным. Если жех= О, то хек истинно для обоих значении.". Если переменная х находится в области действия некоторой квантификации х, то это вхождение х называется связпнным, в противном случае — свободным.

Пример 11.8. Каждое использование переменной в КБФ (11.1) является связанным, поскольку находится в области действия квантора с этой переменной. Например, область действия переменной у, квантифицированной в (Зу)(ху), — это выражение ху. Таким образом, данное вхождение у связано. Вхождение х в ху также связано из-за квантора (Чх), областью действия которого является все выражение.