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

П Значением КБФ без свободных переменных является или О, или 1 (ложь или истина, соответственно). Значение такой КБФ можно вычислить с помощью индукции по длине 1. (Е). Тогда Е имеет ллину и — 2, и значение Е может быть вычислено как О или 1. Значение (Е) совпадает с ним. 2. ~Е. '1'огда Е имеет длину и — ! и его значение можно вычислить. Если Е = 1, то — Е = О, и наоборот.

3. ЕЕ Выражения Е и Г короче и и могут быть вычислены. Значением ЕГ будет 1, если оба выражения Е и Е имеют значение 1, и О, если хотя бы одно из них равно О. 4. Е+ Е Выражения Е и Е короче и и могут быть вычислены. Значением Е+ Е будет 1, если хотя бы одно из Е и Г имеет значение 1, и О, если оба равны О. 5. (Чх)(Е). Все вхождения х в Е заменяются значением О для получения выражения Е~~, а также все вхождения х в Е заменяются значением 1 для получения Еь Заметим, что выражения Ея и Е,: а) не имеют свободных переменных, поскольку любое вхождение свободной переменной отличалось бы от х и было бы свободным в Е; б) имеют длину и — б, что меньше и. Вычисляются Е„и Еп Если у обоих значение 1, то (Чх)(Ц имеет значение 1; в противном случае — О.

Отметим, каким образом это правило отражает интерпретацию (вх) с помощью "для всех х". б. (Зх)(Е). Как и в п. 5, строятся и вычисляются Е, и Еь Если хотя бы у одного из них значение 1, то значением (Зх)(Е) будет 1; в противном случае — О, Отметим, каким образом это правило отражает интерпретацию (Зх) с помощью "существует х".

Пример 11.9. Вычислим КБФ (1!.!). Она имеет вид («вх)(Е), поэтому сначала вычислим Ев. (11.2) (Зу)(оу)- (Чя)( О-:я). Значением этого выражения будет 1, если хотя бы один из операндов ИЛИ вЂ” (Зу)(бу) и (Чс)(- О+ х) — имеет значение!. Для вычисления (Эу)(бу) нужно подставить у = О ну = 1 в полвыражение Оу и проверить, что хотя бы одно из двух получаемых выражений имеет значение 1. Однако и О л О, и О л 1 имеют значение О, поэтому значением (Зу)(Оу) будет О. К счастью, значением (ек)(- О ь я) будет 1 — это видно при подстановке я = О и = = 1. Поскольку —,0 = 1, в этих двух случаях вычисляется 1 м О и 1 м 1, т.е. 1.

Поэтому («гх)(- О + Я) имеет значение 1. Итак, значением Ев, т.е. выРажениЯ (11.2), ЯвлЯетсЯ 1. Еще нужно также проверить, что выражение Е,— (11.3) (аД!у)-~. (Ч )( — «1+ я), 5 Отметим. что используется альтернативная запись И и ИЛИ. чтобы выражения с О и 1 не смотрелись как многорпрялные целые числа или арифметические выражения. Надеемся, читатель воспринимает обе нотации. 493 11.3. ПРОБЛЕМА, ПОЛНАЯ ДЛЯ РЯ получаемое при подстановке х = 1 в (11.1), также имеет значение 1.

Значением выражения (Чу)!!у) будет 1, что видно при подстановке у = 1. Таким образом, Еь т.е. выражение (11.3), имеет значение 1, и значением всего выражения !! 1.1) является 1. П 11,3.4. РЬ-полнота проблемы КБф Теперь определим проблему формулы с квантороми: выяснить, имеет ли данная КБФ без свободных переменных значение 1.

Эта проблема сокращенно обозначается КБФ, хотя КБФ продолжает применяться и как сокращение для термина "булева формула с кванторами". Контекст всегда позволит избежать двусмысленности. Будет показано, что проблема КБФ полна для Р$. Доказательство сочетает идеи теорем 10.9 и 11.5. Из теоремы 10.9 берется идея представления вычисления МТ с помощью логических переменных, каждая из которых говорит, имеет ли определенная клетка определенное значение в определенный момент времени. Однако в теореме 10.9 речь шла о по- линомиальном времени, поэтому там присутствовало полиномиальное количество переменных.

Мы были в состоянии за полиномиальное время породить выражение, говорившее, что МТ допускала свой вход. Когда же речь заходит о полиномиальном пространстве, число МО в вычислении может быть экспоненциальным относительно размера входа, по- этому за полиномиальное время записать выражение, говорящее о корректности вычисления, невозможно. К счастью, теперь у нас есть более мощный язык, и возможность квантификации позволяет записать полиномиальную по длине КБФ, которая говорит, что МТ с полиномиально ограниченным пространством допускает свой вход.

Для выражения идеи того, что одно МО превращается в другое за некоторое большое число переходов, нз теоремы 11.5 берется принцип "рекурсивного дублирования*'. Для того чтобы сказать, что МО 7 превращается в МО,У за т переходов, утверждается, что существует МО К, получаемое из! за т2 переходов и приводящее к,У еше за т,'2 переходов. Язык булевых формул с кванторами позволяет выражать такого рода факты в пределах полиномиальной длины, даже если т экспоненциально относительно длины входа.

Перед проведением доказательства, что каждый язык из Ро' полиномиально сводим к КБФ, нужно показать, что КБФ принадлежит РЯ Эта часть доказательства РБ-полноты сама по себе сложна и выделяется в следующую теорему. Теорема 11.10. КБФ принадлежит Ро. Доказательство. В разделе 11.3.3 был описан рекурсивный процесс вычисления КБФ Е. Этот алгоритм можно реализовать с использованием магазина, хранимого на ленте МТ, как в доказательстве теоремы 11.5. Пусть и — длина Е. Тогда для Е создается запись длиной О(п), включающая саму Е и пространство для записи обрабатываемых подвыражений Р'. Процесс вычисления объясняется для двух из шести возможных вариантов выражения Е'.

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

Тогда выполняем следующее: а) создаем выражение Е, путем подстановки 0 вместо каждого вхождения х и помешаем Е, в собственную запись справа от записи для Е; б) рекурсивно вычисляем Е;, в) если значением Е, является 1, то возвращаем 1 как значение Р', г) если значение Ев — О, то создаем выражение Е„подставляя 1 вместо х в Е; д) запись лля Е, замещаем записью для Е, и рекурсивно вычисляем ЕБ е) в качестве значения Е возвращаем значение Еь Описание подобных шагов вычисления Е в ее остальных четырех формах — Р',Ев -Е, (Е), (Чх)(Е) — предоставляется читателю. Базисный случай, когда формула является константой, требует лишь возвращения этой константы без создания записей на ленте.

Заметим, что в любом случае справа от записи для выражения, длина которого т, присутствует запись для выражения меньшей длины. Отметим, что, хотя в случае 1 вычисляются два различных подвыражения Е, и Гв это делается последовательно. Таким образом, записи для Е, и его подвыражений и записи для Ез и его подвыражений не присутствуют на ленте одновременно. То же верно и для Ев и Е, в п. 2. Следовательно, если мы начинаем с выражения длиной и, в магазине не может быть более и записей. Каждая запись имеет длину 0(л). Поэтому размер ленты не превышает 0(п~).

Теперь у нас есть конструкция для МТ с полиномиально ограниченным пространством, допускающей КБФ; предел ее пространства является квадратичным. Заметим, что время работы этого алгоритма обычно экспоненциально относительно я, поэтому он не полиномиален по времени. П Обратимся к сведению произвольного языка Е из Ро к проблеме КБФ. Нам хотелось бы использовать пропозициональные переменные у„„, как в теореме 10.9, для утверждения, что вузй позиции Бго МО находится символ А. Однако, поскольку МО экспоненци- альное число, нельзя взять вход длиной п и даже просто выписать эти переменные за время, полиномиальное относительно л. Воспользуемся квантификацией, чтобы с помощью одного и того'же множества переменных представлять много различных МО. Эта идея раскрывается в доказательстве следующей теоремы. Теорема 11.11. Проблема КБФ РБ-полна.

11.3. ПРОБЛЕМА, ПОЛНАЯ ДЛЯ РБ 495 Доказательство. Пусть 1. — язык из РЯ, допускаемый недетерминированной МТ М, которая при обработке входа длиной и использует не более р(п) клеток. По теореме 11.3 существует константа с, для которой М допускает вход длиной и в пределах с ""' переходов (если допускает). Опишем, как за полиномиальное время по входу и длиной и построить КБФ Е без свободных переменных, имеющую значение 1 тогда и только тогда, когда и принадлежит ЦМ). При записи Е нам понадобится ввести полиномиальное число переменных МО, которые представляют собой множества переменных унь утверждающих, что уья позиция представляемого МО содержит символ А (1 может изменяться от О до р(п)).

А есть либо ленточный символ, либо состояние М Таким образом, число пропозициональных переменных в переменном МО полиномиально относительно и. Предположим, что все пропозициональные переменные в разных переменных МО различимы, т.е. ни одна из них не принадлежит двум разным переменным МО. Поскольку существует лишь полиномиальное число переменных МО, общее количество пропозициональных переменных по- линомиально. Удобно ввести нотацию (Э1), где 1 — переменное МО. Этот квантор записывается вместо (Зх,)(Лх,)...(Зх ), где х,, х,, ..., х — все пропозициональные переменные в переменном МО 1.

Аналогично вместо применения квантора Ч ко всем пропозициональным переменным в 1 записывается (е)). КБФ, которая строится для и, имеет вид (Э1е)(311)(5 д )У ж Р). Подвыражения этой формулы имеют слелуюший смысл. 1. 1е и 1, — переменные МО, представляющие начальное и допускающее МО, соответственно. 2.