Сложность вычислений.

Y
вводный спецкурс

В.Н. Крупский

T
i
sk

I
up

X
Kr

aft
E
r
V.

,d
L
tes
P
No
M
re
ctu
CO

Москва 2003, 2005

Le
 В.Н. Крупский
Сложность вычислений.

Y
Курс лекций

T
i
Учебное пособие написано по материалам полугодового спецкурса,

sk
читавшегося автором на механико-математическом факультете МГУ им.
М.В. Ломоносова для студентов и аспирантов кафедры математической

I
логики и теории алгоритмов, а также специальности "Защита информа-
up
ции". Излагаются оcновные идеи и методы теории сложности вычисле-
ний.

X
Для студентов, аспирантов и специалистов, занимающихся анализом
эффективности алгоритмов.
Kr

aft
E
r
V.

,d
L
tes
P
No
M
re
ctu
CO
Le
 Y
Оглавление

T
i
I МОДЕЛИ ВЫЧИСЛЕНИЙ. sk 7

I
1 Машины Тьюринга. 9
up
1.1 Неформальное введение. . . . . . . . . . . . . . . . . . . . . 9
1.2 Модели Тьюринга. . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Время и память.

X
1.3 Многоленточные машины Тьюринга. . . . . . . . . . . . . .

17
13
Kr

2.1 Время и зона машины Тьюринга. . . . . . . . . . . . . . . . 17

aft
2.2 Цена сокращения алфавита. . . . . . . . . . . . . . . . . . . 19
E
2.3 Цена сокращения количества лент. . . . . . . . . . . . . . . 21

r
3 Универсальные машины Тьюринга. 25
V.

,d
3.1 МТ, универсальная для класса C. . . . . . . . . . . . . . . . 25
L
3.2 Конструкция универсальной машины. . . . . . . . . . . . . 26
3.3 Теоремы об иерархии. . . . . . . . . . . . . . . . . . . . . . . 28
tes
4 Моделирование других языков. 31
4.1 Схема моделирования. . . . . . . . . . . . . . . . . . . . . . 31
P

4.2 Моделирование RAM. . . . . . . . . . . . . . . . . . . . . . . 32

4.3 Моделирование булевых схем. . . . . . . . . . . . . . . . . . 34
No
M

II СЛОЖНОСТНЫЕ КЛАССЫ. 37

5 Класс P . 39
re

5.1 Определение класса P . . . . . . . . . . . . . . . . . . . . . . 39

5.2 Примеры: целочисленная арифметика. . . . . . . . . . . . . 40
5.3 Примеры: арифметика остатков. . . . . . . . . . . . . . . . 42
ctu

5.4 Примеры: сложение и умножение матриц. . . . . . . . . . . 43

CO

5.5 Примеры: связность в графе. . . . . . . . . . . . . . . . . . 44

3
Le
4 Оглавление

6 Класс P/P oly. 45

6.1 Распознавание языков последовательностями булевых схем. 45

Y
6.2 Континуальность класса P/P oly. . . . . . . . . . . . . . . . 46
6.3 Включение P ⊂ P/P oly. . . . . . . . . . . . . . . . . . . . . 47

7 Класс N P . 51
7.1 Определение класса N P . . . . . . . . . . . . . . . . . . . . . 51

T
7.2 О проблеме P 6= N P . . . . . . . . . . . . . . . . . . . . . . . 53

i
7.3 Примеры задач класса N P . . . . . . . . . . . . . . . . . . . 54

sk
8 Примеры N P -полных задач. 57

I
8.1 Сводимость ≤pm (Карп), N P -полнота. . . . . . . . . . . . . 57
up
8.2 N P -полнота задачи SAT . . . . . . . . . . . . . . . . . . . . 58

X
8.3 N P -полнота задачи о клике. . . . . . . . . . . . . . . . . . . 60
8.4 N P -трудность целочисленного ЛП . . . . . . . . . . . . . . 61
Kr

9 Класс BP P . 63

aft
9.1 Вероятностные вычисления. . . . . . . . . . . . . . . . . . . 63
E
9.2 Частотные распознаватели. . . . . . . . . . . . . . . . . . . 64
9.3 Включение BP P ⊂ P/P oly. . . . . . . . . . . . . . . . . . . 66

r
10 Распознавание простоты. 69
V.

,d
10.1 Сведения из теории чисел. . . . . . . . . . . . . . . . . . . . 69
L
10.2 Извлечение корней. . . . . . . . . . . . . . . . . . . . . . . . 70
10.3 Вероятностный алгоритм . . . . . . . . . . . . . . . . . . . . 70
tes
10.4 Верификация алгоритма. . . . . . . . . . . . . . . . . . . . . 71
10.5 Оценка сложности. . . . . . . . . . . . . . . . . . . . . . . . 73
P
No

11 Конечные игры и класс P H. 75

11.1 Конечные игры. . . . . . . . . . . . . . . . . . . . . . . . . . 75
11.2 Определение класса P H. . . . . . . . . . . . . . . . . . . . . 76
M

11.3 Замкнутость относительно ∩, ∪ и (·)c . . . . . . . . . . . . . 78

re

12 Полиномиальная иерархия. 81
12.1 Классы полиномиальной иерархии . . . . . . . . . . . . . . 81
12.2 Структурные свойста. . . . . . . . . . . . . . . . . . . . . . . 82
ctu

12.3 Пример. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
CO

12.4 Включение BP P ⊂ Σp2 ∩ Πp2 . . . . . . . . . . . . . . . . . . . 85

Le
Оглавление 5

13 Класс P SP ACE. 89
13.1 Класс P SP ACE и игры. . . . . . . . . . . . . . . . . . . . . 89

Y
13.2 Моделирование игры. . . . . . . . . . . . . . . . . . . . . . . 90
13.3 Моделирование на полиномиальной памяти. . . . . . . . . . 91
13.4 Игровая характеризация класса P SP ACE. . . . . . . . . . 92

14 Σpn -, Πpn - и P SP ACE-полные задачи. 95

14.1 Квантифицированные булевы формулы . . . . . . . . . . . 95

T
i
14.2 Полные задачи для классов P H. . . . . . . . . . . . . . . . 97

Литература
sk
14.3 Пример P SP ACE-полной задачи. . . . . . . . . . . . . . . 98

101

I
up

X
Kr

aft
E
r
V.

,d
L
tes
P
No
M
re
ctu
CO
Le
 6
CO V.
M Kr
up
Le
P L sk
i
ctu E
re X
Оглавление

No
tes
,d
IT
aft r Y
CO V.
M Kr

7
up
Часть I
Le
P L sk
i
ctu E
re МОДЕЛИ ВЫЧИСЛЕНИЙ.
X
No
tes
,d
IT
aft r Y
CO V.
M Kr
up
Le
P L sk
i
ctu E
re X
No
tes
,d
IT
aft r Y
 Y
Глава 1

T
i
Машины Тьюринга. sk

I
up
1.1 Неформальное введение.

X
Неформальное понятие модели вычислений предполагает задание языка
программирования вместе с его операционной семантикой, т.е. объясне-
Kr

нием того, каким образом программе сопоставляется процесс вычисле-

aft
ний.
E
Процесс вычислений, развиваясь во времени (которое дискретно), по-
требляет различные (разнородные) ресурсы. Предполагается, что вели-

r
чина потребленного к данному моменту ресурса измеряется натуральны-
V.

,d
ми числами и не может быть бесконечной, т.е. бесконечный ресурс тре-
буется только для никогда не заканчивающегося процесса. Удобно (хотя
L
не столь существенно) также считать, что каждый никогда не заканчи-
вающийся процесс потребляет бесконечное количество каждого ресурса,
tes
т.е.
P

Ресурс < ∞ ⇔ процесс вычисления заканчивается.

No

Обычно модель вычислений задает способ подсчета использованных

ресурсов в каждом конечном вычислении. Т.е.
M

• функция Compl : (program, input) 7→ resourse – вычислима,

• отношение Compl(p, i) < n – разрешимо.

re

Основные (но не единственные) ресурсы – время и память. Но для каж-

дой модели вычислений они свои !
ctu

Как используют модель вычислений для оценки трудоемкости ал-

CO

горитмов: хорошо реализуют алгоритм в виде программы p на языке

9
Le
10 Глава 1. Машины Тьюринга.

программирования данной модели, выбирают ресурс r (из числа опре-

деленных в модели) и ищут верхние оценки f (n) на величину затрат.

Y
Например, в худшем случае:

max Complr (p, i) < f (n).

size(i)=n

Основное противоречие: точные оценки такого рода интересны

T
для моделей вычислений с реалистичными языками программирования,

i
для которых получение каких-нибудь теоретических оценок очень труд-
но. Выходы:
sk
• (машинно зависимый, зависит от "железа", а потому результаты

I
быстро устаревают) Численный эксперимент.
up

X
• (не вполне честный) Огрубления в определении ресурса. Например,
в качестве времени для C – подсчет только количества выполняе-
мых арифметических операций (или только сравнений).
Kr

aft
• Построение честных оценок для более простой "игрушечной"модели
и учет замедления при компиляции в реальный язык.
E
r
Пример. Пусть “игрушечная” модель вычисления M допускает ком-
V.

,d
пилятор программ в C
L
compiler : pM 7→ pC ,
tes
про который доказано (одна теорема для пары моделей), что
P

T imeC (pC , i) < (T imeM (pM , i))5 + 1000.

No

Если мы установим, что временная сложность некоторой задачи в M

есть O(n2 ), то получим верхнюю оценку O(n10 ) в C. Это загрубленная,
M

но честная оценка.
Как относится к таким оценкам. Конечно, показатель степени
весьма неточен, но то, что время есть степенная функция, а не экспонен-
re

та – абсолютно точно! Значит, использовать этот подход разумно тогда,

когда важна разница между многочленом и экспонентой, а не между n2
и n3 . Тогда и теорему про компилятор можно доказывать не в самой
ctu

сильной форме (например, не уточняя показатель степени), когда она в

CO

большинстве случаев оказывается очевидной.

Le
1.2. Модели Тьюринга. 11

Наблюдение. Для реальных универсальных языков программиро-

вания и большинства универсальных "игрушечных"(не специально ис-

Y
порченных) языков компиляция одного в другой замедляет по времени
не более, чем полиномиально, и увеличивает потребность к памяти не
более, чем линейно. Именно на это положение дел следует рассчитывать
в приложениях теории сложности и внутри самой теории.

T
i
1.2 Модели Тьюринга.

sk
Это семейство моделей вычислений наиболее честно отражает время вы-
числений. Возможных вариантов определения много. Машина Тьюринга

I
состоит из управляющего устройства (УУ) и потенциально бесконечной
up
внешней памяти, структура которой не меняется со временем. Она снаб-

X
жена программой, задающей правила ее функционирования.

Программа
Kr

УУ Память

aft
E
Память разбита на одинаковые ячейки, предназначенные для хра-
нения букв фиксированного конечного алфавита (одна буква в ячейке).

r
Имеется одна или несколько (конечное число) читающе-пишущих голо-
V.

,d
вок. В каждый момент времени головка обозревает одну ячейку памяти.
L
За один такт работы головка может изменить содержимое этой ячейки
и переместиться к одной из соседних (или остаться на месте). Функ-
tes
ционированием головок управляет УУ. В каждый момент времени УУ
находится в одном из фиксированного конечного множества внутрен-
P

них состояний. Один такт работы состоит в следующем: машина читает

содержимое обозреваемых ячеек и внутреннее состояние, выбирает из
No

программы инструкцию, однозначно определяемую этими данными, и

исполняет ее. В инструкции сказано, каким должно стать новое внут-
M

реннее состояние, какие буквы должны быть записаны в обозреваемые

ячейки и куда должны переместиться головки.
Варианты определения различаются геометрией памяти (это суще-
re

ственно, т.к. за один шаг головкам разрешается переместиться только

в соседние ячейки). В простейших моделях память представляет собой
ленту с одной головкой, бесконечную в одну
ctu
CO

...
Le
12 Глава 1. Машины Тьюринга.

или обе стороны

... ... .

Y
В теории сложности обычно используют многоленточные машины Тью-
ринга – конечный набор лент с одной головкой на каждой (более де-
тальное описание см. ниже). Рассматривались также машины Тьюринга
с "многомерной"памятью (напр., в виде клетчатой плоскости) и различ-
ные "многоглавые"варианты (несколько головок на одной связной ком-

T
i
поненте памяти). Можно показать, что все эти варианты моделируют
друг друга с полиномиальным (квадратичным) замедлением по време-
sk
ни и линейным увеличением памяти.
Вычислительные возможности машин Тьюринга достаточно хорошо

I
изучены. Их качественная характеризация состоит в описании класса
up
всех функций, вычислимых на машинах Тьюринга. Речь идет о частич-
ных словарных функциях f : Σ∗ → Σ∗ , где Σ∗ – множество всех слов

X
в конечном алфавите Σ, а термин “частичная функция” означает, что
значение функции f (v) для некоторых слов v ∈ Σ∗ может оказаться
неопределенным. Результат сравнительного изучения запасов вычисли-
Kr

aft
мых словарных функций для различных (не только “игрушечных”) моде-
лей вычислений может быть сформулирован в виде следующего нефор-
мального утверждения:
E
r
Тезис Тьюринга (неформальный): Каждую вычислимую
V.

(программой какого угодно языка программирования) частич-

,d
ную функцию типа Σ∗ → Σ∗ можно вычислить на подходя-
L
щей машине Тьюринга.
tes
Неформальность Тезиса Тьюринга состоит в том, что он не может
быть полностью обоснован математическими средствами (доказан как
P

математическая теорема). В то же время все многочисленные попытки

его опровергнуть, т.е. предложить язык программирования с большими
No

вычислительными возможностями, оказались безуспешными (в резуль-

тате чего в настоящее время подобные проекты считаются абсолютно
M

бесперспективными). Причина невозможности полного математическо-

го обоснования кроется в словах “какого угодно языка программирова-
ния” – они не определяют ни самого семейства языков, о которых идет
re

речь, ни какого-либо свойства этого семейства. Если их заменить на до-

статочно информативное описание семейства языков программирования
(которое необходимо окажется менее общим), то соответствующий част-
ctu

ный случай Тезиса станет обычным, “поддающимся доказательству” ма-

CO

тематическим утверждением.
Le
1.3. Многоленточные машины Тьюринга. 13

Пример. Пусть семейство состоит из языков, C и PASCAL, задан-

ных полным описанием их синтаксиса и операционной семантики. Оба

Y
языка обладают компиляторами в ASSEMBLER, поэтому для обосно-
вания соответствующего частного случая Тезиса Тьюринга достаточно
построить компилятор, преобразующий ассемблерный код в програм-
му для машины Тьюринга. Последнее является весьма трудоемкой, но
абсолютно реалистичной задачей по программированию. Для аккурат-

T
ного математического доказательства потребуется еще верифицировать

i
все три компилятора, т.е. доказать, что они работают правильно.

1.3
sk
Многоленточные машины Тьюринга.

I
up
Ленты бесконечны в обе стороны. Пустые ячейки несут символ #. Есть

X
одна или несколько входных лент (только для чтения), одна или несколь-
ко рабочих лент (можно читать и писать), некоторые из которых можно
объявить выходными. Входной алфавит Σ0 содержится в ленточном Σ
Kr

и не содержит #. Результат (на выходной ленте) есть то слово в алфа-

aft
вите Σ0 , на котором или непосредственно перед которым остановилась
E
головка. Удобно также требовать, чтобы на входных лентах головка не
удалялась от границ входного слова наружу: например, можно ввести

r
ограничительные буквы b и e для обозначения границ входного слова, за
V.

которые головке вылезать запрещается. Начальная конфигурация лент

,d
выглядит так:
L
Входная лента с исходными данными:
tes
...# b 1 0 1 1 e #...
4
P
No

Рабочие ленты:
...# # # # # # #...
M

4
...# # # # # # #...
4
re

...# # # # # # #...
4
ctu

Работа машины описывается тремя конечными функциями (k – коли-

CO

чество лент, Q – фиксированное заранее конечное множество состояний

Le
14 Глава 1. Машины Тьюринга.

УУ):

Y
α : Q × (Σ∗ )k → Q – новое состояние
∗ k
β : Q × (Σ ) → (Σ )∗ k – новое содержимое ячеек
γ : Q × (Σ∗ )k → {N, L, R}k – движения головок

Их удобно записывать в виде программы – набора непротиворечивых

команд вида:

T
i
qā 7→ α(q, ā)β(q, ā)γ(q, ā)

sk
Непротиворечивость набора означает, что в нем нет двух команд с оди-
наковой левой частью qā. Для сокращения письма предполагают также,
что если команда с левой частью qā не выписана явно, то она все-таки

I
есть в программе, но имеет специфический вид qā 7→ qā N . . . N . Такие
up
команды тривиальны, т.к. не вызывают никаких действий.

X
Пример. На Рис.1.1 приведена программа машины Тьюринга с од-
ной входной и одной рабочей лентой, которая переписывает исходное
двоичное слово в обратном порядке.
Kr

aft
Полная спецификация многоленточной машины Тьюринга есть на-
бор
E
< Q, Σ, α, β, γ, q. , q. > .

r
Если к ней добавлен входной алфавит Σ0 ⊂ Σ \ {#, b, e}, выделены вход-
V.

,d
ные (k0 штук) и выходные (l0 штук) ленты и α в самом деле не меняет
L
содержимое входных лент, то получаем вычислитель (частичной) функ-
ции f : (Σ∗0 )k0 → (Σ∗0 )l0 . Для вычисления значения функции – вектора
tes
(w1 , . . . , wl0 ) = f (v1 , . . . , vk0 ) надо записать на входных лентах слова bvi e,
запустить машину и дождаться остановки, после чего считать с j-той
выходной ленты то слово в алфавите Σ0 , на которое указывает головка.
P

Это wj . Если головка остановилась не на букве алфавита Σ0 , то резуль-

No

тат – пустое слово. Если машина работает бесконечно долго, то значение

f (v1 , . . . , vk0 ) не определено.
M

Замечание. Конечное множество состояний на самом деле может

представлять любую ограниченную (для данной машины) структуру
re

данных. Это имитирует статически распределенную память с возможно-

стью за один шаг переприсваивать ее всю целиком. Единственное огра-
ничение – новое состояния определяется (заранее) однозначно по преды-
ctu

дущему состоянию и содержимому обозреваемых ячеек ленты.

CO
Le
1.3. Многоленточные машины Тьюринга. 15

T Y
Программа:

i
7→ 7→
q0 b#
q0 0#
q0 1#
7→
7→ sk
q0 b# RN
q0 0# RN
q0 1# RN
q1 0#
q1 1#
q1 b#
7→
7→
q1 00 LR
q1 11 LR
q2 b# N N

I
q0 e# 7→ q1 e# LN
up
Функционирует она так:

X
# b 1 0 1 1 e #
4 Начальное состояние
# # # # # # # # q0 .
Kr

aft
E Состояние q0 переме-
# b
1 0 1 1 e #
щает головку на вход-

r
−→ 4
ной ленте к концу
V.

,d
# # # # # # # #
слова и меняется на
4
L
tes q1 .

Состояние q1 пере-
# b 1 0 1 1 e # мещает обе головки
4 ←− в противоположных
P

# 1 1 0 1 # # # направлениях, копи-
−→ 4 руя биты со входной
No

ленты на рабочую.
M

Рис. 1.1: Пример машины Тьюринга.

re
ctu
CO
Le
 16
CO V.
M Kr
up
Le
P L sk
i
ctu E
re X
Глава 1. Машины Тьюринга.

No
tes
,d
IT
aft r Y
 Y
Глава 2

T
i
Время и память. sk

I
up
2.1 Время и зона машины Тьюринга.

X
Время TM (input) – это число шагов в вычислении машины Тьюринга
M на входе input. Шагом считается исполнение одной команды, т.е. соот-
Kr

ветствующие изменения состояния и содержимого обозреваемых ячеек

aft
памяти, а также перемещения головок, происходят за 1 времени.
E
Зона, память SM (input) определяется как максимум по всем ра-
бочим лентам количества использованных ячеек к моменту остановки

r
машины M на входе input. Если машина никогда не заканчивает работу,
V.

,d
то полагаем зону бесконечной. Ячейка считается использованной, если
L
в ней побывала головка.

∗ ∗ ∗ ∗ ∗
tes
∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗
P

∗ ∗ ∗
зона
No

Выбор максимума в определениии зоны вместо более естественной

M

меры – суммарного количества использованных ячеек – значительно

упрощает расчеты, но практически не сказывается на получаемых оцен-
ках. В то же время оказывается существенным исключение входных лент
re

из подсчета. Оно позволяет адекватно оценивать малые затраты памя-

ти, когда вычисление требует рабочих ячеек меньше, чем длина входного
слова.
ctu

Проблема с определением зоны: из определения непонятно, как

CO

алгоритмически проверять условие “SM (input) < s” (это было одним из

17
Le
18 Глава 2. Время и память.

желанных свойств определения меры сложности). На самом деле такой

алгоритм существует. Он основан на следующей оценке:

Y
Теорема 2.1 По описанию машины Тьюринга M можно вычислить
константу C такую, что если процесс вычисления M на некотором
входе заканчивается за t шагов с зоной s, то

s ≤ t ≤ n k0 C s ,

T
i
sk
где n – максимум длин входных слов, k0 – число входных лент.

Доказательство. Левое неравенство: за один шаг на рабочей ленте рас-

I
ходуется не более одной ячейки.
up
Докажем правое неравенство. Для данного вычисления определим

X
понятие конфигурации в данный момент времени: это состояние, содер-
жимое всех лент и положение всех головок (относительно левой границы
блока использованных на данной ленте ячеек). Легко видеть, что если в
Kr

два разных момента времени мгновенные конфигурации совпадают, то

aft
вычисление зациклилось и никогда не закончится. Значит, для нашего
(заканчивающегося) вычисления все конфигурации различны. Если зона
E
вычисления есть s, вход фиксирован, то различных возможных конфи-
гураций не более, чем

r
V.

,d
|Q| · |Σ|(k−k0 )s · (n + 2)k0 · sk−k0 ≤ nk0 C s .
L
Здесь |Q| – количество состояний, |Σ| – количество букв в ленточном
алфавите, k – общее количество лент. Сомножитель |Σ|(k−k0 )s оценивает
tes
сверху число различных вариантов заполнения лент буквами алфавита
|Σ|, а произведение (n + 2)k0 · sk−k0 – количество возможных расположе-
P

ний головок.
No

Число шагов t не больше числа различных конфигураций, т.е. оце-

нивается сверху этой же величиной nk0 C s .
M

Алгоритм проверки условия “SM (input) < s”:

re

1. По M, input, s вычисляем T = nk0 C s и моделируем вычисление

M (input) на T шагов.
ctu

2. Если оно закончилось и фактическая зона оказалась меньше s, то

CO

возвращаем true; иначе – f alse.

Le
2.2. Цена сокращения алфавита. 19

2.2 Цена сокращения алфавита.

Y
Теорема 2.2 Для вычисления функции типа

({0, 1}∗ )k0 → ({0, 1}∗ )l0

достаточно ленточного алфавита {0, 1, #, b, e}. При переходе к такому

алфавиту зона и время изменяются линейно. (Буквы b и e используют-

T
i
ся только как ограничители на входных лентах.)

sk
Замечание. При прямой конструкции добавится l0 рабочих лент
(выходных). Если не добавлять, то время может возрасти не более, чем

I
квадратично.
up
Доказательство. Для простоты изложения рассмотрим случай одной

X
рабочей ленты. Пусть исходная машина уже модифицирована так, что
на рабочей ленте она не оставляет "пустыми"(т.е. #) ячейки, в кото-
рых бывала. (Это можно сделать с помощью введения новой буквы * –
Kr

двойника для #.)

aft
Фиксируем подходящее число m ≈ log2 |Σ| так, чтобы каждую букву
ленточного алфавита Σ можно было однозначно закодировать блоком из
E
m бит. Фиксируем такое кодирование. Его удобно представлять в виде
бинарного дерева D глубины m: пути из корня к листьям – коды; на

r
листе – соответствующая буква алфавита Σ.
V.

,d
* a0
L
0

0 
* H
 1 H j a1
HH
0* a2
tes
1 H
jHH
1 j a3
P

Каждой ленточной (без состояния) конфигурации исходной машины

сопоставим ленточную конфигурацию новой машины, заменив на рабо-
No

чей ленте буквы алфавита Σ кроме # на их коды (головки в началах

соответствующих блоков). Зона возрастет в m раз.
M

. . . a5 . . . . . . 10010 . . .
7−→
4 4
re

Каждый шаг исходной машины будет моделироваться 2m шагами

(изменение буквы ai на aj ) и еще m шагов потребуется для перемеще-
ctu

ния головки к соседнему блоку (если необходимо). Основное состояние

CO

моделирующей машины состоит из

Le
20 Глава 2. Время и память.

1. состояния исходной машины,

2. переменной для хранения одного символа ∈ {N, L, R},

Y
3. переменной-счетчика для хранения одного из чисел
0, . . . , m − 1,

4. пометки "read", "write"или "go",

T
5. бинарного дерева D c выделеной вершиной. В начальный момент

i
моделирования шага выделен корень, а пометка есть "read".

sk
Заметим, что число состояний конечно и не зависит от входа.
Этап "read". Первые m шагов моделирования состоят в том, что го-

I
ловка сканирует код буквы слева направо, а в состоянии меняется толь-
up
ко выделенная вершина дерева D – она перемещается по пути, соот-

X
ветствующему считываемому коду. Когда она достигнет листа, на нем
будет написана изменяемая буква ai . Тогда пометка "read"меняется на
"write"и выделенной вершиной становится лист с буквой aj . В этот мо-
Kr

мент меняем хранимое состояние исходной машины и (если необходимо)

aft
производим перемещение головок на входных лентах так, как это дела-
E
ла моделируемая машина. Также определяем и запоминаем требуемое
направление движения головки на рабочей ленте.
Этап "write". Следующие m шагов головка движется по блоку в об-

r
ратном направлении (налево), а выделенная вершина – к корню дере-
V.

,d
ва D. При этом путь, проходимый выделенной вершиной, определяет
L
биты кода буквы aj (справа налево) и они пишутся в соответствую-
щие ячейки блока. Когда выделенная вершина достигает корня, пометка
tes
"write"меняется на "go".
Этап "go". Если запомнен символ движения L или R, то перемещаем
P

головку на m позиций в соответствующем направлении, отсчитывая их

с помошью счетчика. В конце меняем пометку "go"на "read"и переходим
No

к моделированию следующего шага. Если запомнен символ N , то просто

меняем пометку.
M

Заметим, что очередное состояние всегда есть функция от предыду-

щего и очередной считанной буквы, как того и требует формализм.
Отдельные усилия требуются для моделирования поведения машины
re

на границе рабочей зоны – когда головка моделирующей машины в на-

чале шага находится в ячейке с буквой #. Тогда текущий и ближайшие
вправо m − 1 символов # (они обязательно будут такими!) надо заме-
ctu

нить на код буквы # (понадобятся дополнительные состояния), а только

CO

потом выполнять основной шаг.

Le
2.3. Цена сокращения количества лент. 21

Так построенная моделирующая машина делает то же, что и исход-

ная, но выдает ответ в виде последовательности кодов букв 0 и 1. Для де-

Y
кодирования добавляем одну дополнительную выходную ленту и в кон-
це переписываем на нее результат, декодируя в процессе переписывания.
Время на это – m · (длина результата), что не превосходит

m · (время исходного вычисления).

T
i
2.3 sk
Цена сокращения количества лент.

I
up
Замечание. Одна входная и одна выходная ленты (рабочих – много)
моделирует общий случай за счет введения буквы-разделителя. Цена –

X
время на переписывание входа с одной ленты на много и аналогичного
переписывания результата.
Kr

Теорема 2.3 Много рабочих лент моделируются одной с квадратич-

aft
ным замедлением по времени. Зона меняется линейно. Если ленточный
E
алфавит был не однобуквенным, то его удается сохранить.

r
Доказательство. (Набросок.) Пара рабочих лент
V.

,d
L
... a ... b ... 1-ая лента
4
tes
... c ... d ... 2-ая лента
4
P

моделируется одной так:

No

... a 1 c 0 ... b 0 d 1 ...

M

1-ая 2-ая 1-ая 2-ая

Одной ячейке на исходной ленте соответствуют две соседние ячейки на

re

моделирующей. Левая содержит ту же букву, а правая (0 или 1) – при-

знак того, что одна из головок исходной машины обозревает моделиру-
емую ячейку. Такие пары чередуются, т.е. соседним ячейкам на одной
ctu

из исходных лент соответствуют пары, расположенные на расстоянии 2.

CO

Легко видеть, что зона возрастает в два раза.

Le
22 Глава 2. Время и память.

Один шаг исходной машины моделируется двойным проходом по всей

рабочей зоне моделирующей ленты. При движении справа налево опре-

Y
деляются буквы, обозреваемые исходной машиной, а при движении в
обратную сторону имитируются необходимые изменения (замена букв
и перемещение головок). Моделирующее состояние поддерживает счет-
чик для хранения остатка от деления на 4 величины текущего смещения
головки, что позволяет определить, к какой из моделируемых лент от-

T
носится обозреваемая ячейка. При этом в каждой ячейке рабочей зоны

i
головка моделирующей машины бывает не более фиксированного числа

sk
(c) раз, поэтому время работы моделирующей машины не превосходит
c · 2S · T , где T – время, а S - зона исходного вычисления. Т.к. S ≤ T , то
это моделирование приводит к квадратичному замедлению.

I
up
Замечание. Что изменится, если надо избавляться не только от мно-

X
гих рабочих лент, но и от входной ленты, т.е. моделировать вычисления
функции типа {0, 1}∗ → {0, 1}∗ на одноленточной машине? Пусть моде-
лируемая машина уже двухленточная, одна из которых – входная. Надо
Kr

добавить 2 модуля: один будет переписывать входное слово "разряжен-

aft
но",
# c1 c1 . . .
E
4

r
в
V.

,d
# 1 # 1 c1 0 # 0 c2 0 # 0 ...
,
L
1-ая 2-ая 1-ая 2-ая 1-ая 2-ая
а второй – выполнять обратное преобразование с результатом. Все осталь-
tes
ное моделирование сохраняется. Добавление требует полиномиального
времени и линейной зоны (от длины входа и результата).
P

Итог: Каждую вычислимую на многоленточной машине функцию

типа ({0, 1}∗ )k0 → {0, 1}∗ можно вычислить на машине с единственной
No

рабочей лентой и ленточным алфавитом {0, 1} с полиномиальным замед-

лением по времени и линейным увеличением зоны. Для функций типа
M

{0, 1}∗ → {0, 1}∗ моделирующая машина может быть выбрана однолен-
точной (т.е. и без входных лент тоже) с теми же оценками времени и
памяти, если исходное вычисление по крайней мере читает все вход-
re

ное слово (для того, чтобы вклад дополнителных модулей не превышал

остального, достаточно, чтобы время и зона исходного вычисления оце-
нивались снизу линейной функцией от длины входа).
ctu

Конечно, аналогичные факты справедливы и для произвольного ал-

CO

фавита мощности > 1, а также для вектор-функций с размерностью

Le
2.3. Цена сокращения количества лент. 23

значений l0 ≥ 1, если разделить функции рабочей и выходных лент (на-

пример, разрешить на выходной ленте только писать с одновременным

Y
сдвигом головки вправо).

T
i
sk

I
up

X
Kr

aft
E
r
V.

,d
L
tes
P
No
M
re
ctu
CO
Le
 24
CO V.
M Kr
up
Le
P L sk
i
ctu E
re X
Глава 2. Время и память.

No
tes
,d
IT
aft r Y
 Y
Глава 3

T
i
Универсальные машины
Тьюринга.
sk

I
up
3.1

X
Машина Тьюринга, универсальная для клас-
Kr

са C.

aft
Пусть фиксирован ленточный алфавит Σ ⊃ {0, 1}, наборы входных, ра-
E
бочих и выходных лент. Устроим кодирование класса C всех таких машин
Тьюринга словами в алфавите {0, 1}:

r
V.

1. Состояния условимся записывать двоичными записями их номе-

,d
ров, взятыми в кавычках: ‘101’ есть q5 . Пусть начальное состояние
L
всегда имеет номер 1, а заключительное – 0.
tes
2. Машину Тьюринга сначала запишем в виде программы, состоящей
из команд вида
qā 7→ q 0 ā0 D;
P

Программа оказывается словом в фиксированном алфавите про-

No

грамм.
3. Фиксируем однозначное кодирование букв алфавита программ дво-
M

ичными словами фиксированной длины и применим это кодирова-

ние к программе машины Тьюринга M ∈ C. Так определяется код
re

машины Code(M ).

Определение 3.1 Универсальной для класса C называется машина Тью-

ctu

ринга U с дополнительной входной лентой такая, что

CO

U (Code(M ), input) ' M (input) (3.1)

25
Le
26 Глава 3. Универсальные машины Тьюринга.

выполняется для всех M ∈ C и всех входов input ∈ (Σ∗ )k0 .

Y
Замечание. Условие (3.1) означает, что оба вычисления U (Code(M ), input)
и M (input) либо зацикливаются, либо дают одинаковый результат. Ис-
пользованный в определении символ ' есть так называемое условное
равенство. Это традиционный заменитель обычного отношения равен-
ства, когда приходится сравнивать выражения, которые могут оказаться

T
неопределенными. Утверждение a ' b считается истинным в двух слу-

i
чаях: когда оба выражения a и b определены и равны между собой, либо

sk
когда они оба не определены. Во всех остальных случаях утверждение
считается ложным. Отличие от обычного равенства состоит в том, что
когда хотя бы одно из выражений a или b не определено, выражение

I
a = b не является корректным утверждением и не может быть ни истин-
up
ным, ни ложным. Напротив, a ' b всегда есть корректное утверждение.

3.2 Конструкция универсальной машины.

X
Kr

Факт существования универсальной машины немедленно следует из те-

aft
зиса Тьюринга. По коду машины можно алгоритмически восстановить
E
саму машину и применить ее к данному входу, т.е. функция, которую
должна вычислять U , вычислима. Значит, ее можно вычислить на ма-

r
шине Тьюринга.
V.

Нетрудно явно построить универсальную машину U в том же алфа-

,d
вите с одной дополнительной рабочей лентой, для которой время вы-
L
числения U (code(M ), input) лишь в константу раз больше времени вы-
числения M (input) (сама константа зависит от M ; зона может возрасти
tes
не более, чем на аддитивную константу).
P

ленты машины M :
No

input
M

U: рабочие ленты

доп. ленты:
re

Code(M )
состояние M
ctu

На дополнительной рабочей ленте U хранит двоичный код текущего со-

CO

стояния моделируемой машины M , а остальные ленты (кроме дополни-

Le
3.2. Конструкция универсальной машины. 27

тельной входной) она использует так же, как M . Имитация одного шага
M : машина U читает текущее состояние, ищет в Code(M) ту команду, ко-

Y
торую надо выполнить и выполняет (измененное состояние записывается
на место предыдущего). На все это уходит не более (|Code(M )| + |Q|) · c
шагов.
Избавиться от дополнительной входной ленты (для Code(M )) позво-
ляет следующее кодирование пар двоичных слов:

T
i
ha1 . . . an ; b1 . . . bm i := a1 . . . an 01b1 b1 . . . bm bm .

sk
Код машины M можно подавать на вход, добавляя его к содержимо-
му первой из входных лент в удвоенном виде (т.е. на ленту пишется

I
hinput; Code(M )i ). Тогда в начале работы универсальная машина пере-
up
писывает на две дополнительные рабочие ленты input и Code(M ) по

X
отдельности, а затем работает как указано выше.

hinput; Code(M )i
Kr

aft
рабочие ленты

U:
E
доп. ленты:

r
V.

,d
состояние M
L
Избавиться от дополнительных рабочих лент можно с помощью тео-
tes
ремы 2.3. Все это приведет к тому, что универсальная машина для класса
C будет присутствовать в самом классе. Для класса с одной входной
P

лентой определяющее ее равенство будет выглядеть

No

U (hinput ; Code(M )i) ' M (input), M ∈ C, (3.2)

M

но время моделирования согласно теореме 2.3 возрастет квадратично, а

зона – линейно. Тем самым установлена следующая теорема.
re

Теорема 3.2 В классе C существует универсальная в смысле (3.2) ма-

шина U для этого класса. Для нее
ctu

TU (hinput ; Code(M )i) = O( (TM (input))2 ),

CO

SU (hinput ; Code(M )i) = O( SM (input) ).

Le
28 Глава 3. Универсальные машины Тьюринга.

Замечание. Время моделирования можно несколько улучшить – до

O(T log T ) за счет того, что длина содержимого устраняемых рабочих

Y
лент в процессе моделирования машины M остается ограниченной и
оставшейся головке удается таскать все эти данные по ленте с собой.

3.3 Теоремы об иерархии по времени и по зоне.

T
Вопрос. Когда добавочный ресурс в самом деле увеличивает вычисли-

i
тельные возможности?

sk
Фиксируем класс C. Ограничимся случаем одной входной и одной
выходной ленты. Пусть f – тотальная неубывающая неограниченная вы-

I
числимая функция из N в N . Определим классы T IM E(f ) и SP ACE(f )
как семейства всех функций типа Σ∗ → {0, 1}, вычислимых на машинах
up
из класса C с условием

или

X
TM (v) < f (|v|) для достаточно больших |v|
Kr

aft
SM (v) < f (|v|) для достаточно больших |v|
соответственно.
E
Вопрос уточняется следующим образом: найти условия на поряд-
ки роста функций f, g, достаточные для выполнения строгого включе-

r
ния
V.

,d
T IM E(f ) ⊂ T IM E(g)
L
6=
(3.3)
(соотв., SP ACE(f ) ⊂ SP ACE(g) ).
6=
tes
Результаты, устанавливающие такие оценки, называются теоремами
об иерархии.
P

Способ получения теорем об иерархии.

No

Функция f называется конструируемой по времени (по зоне), если

существует машина Тьюринга M , для которой
M

TM (v) = f (|v|) ( соотв., SM (v) = f (|v|) ).

Пусть f конструируема по времени (или по зоне) машиной M0 . Рас-

re

смотрим следующую модификацию Uf универсальной машины U . К соб-

ственным лентам U в качестве дополнительных рабочих добавлены лен-
ты машины M0 . Сначала вход копируется на бывшую входную ленту
ctu

M0 , после чего обе машины M0 и U (в составе одной Uf ) запускаются

CO

параллельно.
Le
3.3. Теоремы об иерархии. 29

ленты U :
hinput ; Code(M )i

Y
Uf :
ленты M0 :

T
i
sk
Машина M0 служит таймером – как только она останавливается,
прерываем работу U тоже. При этом синхронизируем работу машин U

I
и M0 таким образом, чтобы 1 шаг машины M0 соответствовал 1 шагу
up
моделируемой машины M , т.е. U делает все шаги, моделирующие 1 шаг

X
M , после чего M0 делает 1 шаг, и т.д. Результат читаем с выходной
ленты U и меняем на противоположный: 0 на 1, а все остальное – на 0.
Легко видеть, что функция
Kr

aft
h(v) = Uf (hv; vi)
E
тотальна, вычислима, имеет тип Σ∗ → {0, 1}, но не лежит в T IM E(f )
(соответственно, в SP ACE(f )). В самом деле, если бы h ∈ T IM E(f ),

r
то добавлением в программу вычисляющей ее машины "лишних"команд
V.

,d
можно добиться выполнения условия TM (v) < f (|v|) (или аналогичного
L
для зоны) уже при v = Code(M ). Но тогда

h(Code(M )) = M (Code(M )) = U (hCode(M ); Code(M )i)

tes
6= Uf (hCode(M ); Code(M )i)

по построению. Противоречие.
P

Остается найти верхнюю оценку времени (соотв., зоны), достаточную

No

для вычисления функции h. Рассмотренное ранее довольно грубое моде-

лирование приводит к оценкам вида (f (n))C для времени и C · f (n) для
памяти (константа C извлекается из конструкции). Это означает, что
M

строгие включения (3.3) выполняются для всех функций g, растущих

быстрее этих оценок. Более точные оценки следующие:
re

Теорема 3.3 Для выполнения (3.3) достаточно, чтобы функция g удо-

влетворяла условию
ctu

f (n) log2 f (n)

CO

= o(1) (для времени)

g(n)
Le
30 Глава 3. Универсальные машины Тьюринга.

или
f (n)
= o(1) (для памяти),

Y
g(n)
причем функция f (n) ≥ n должна быть конструируемой.

Непосредственным программированием можно показать, что задава-

емые простыми формулами арифметические функции – конструируемы,

T
поэтому

i
T IM E(n) ⊂ T IM E(n2 ) ⊂ T IM E(n3 ) ⊂ . . .

sk
6= 6=
⊂ T IM E(2n ) ⊂ T IM E(3n ) ⊂ . . . ,
6= 6= 6=
6=

I
SP ACE(n) ⊂ SP ACE(2 · n) ⊂ . . .
6= 6=
up
⊂ SP ACE(n2 ) ⊂ . . . ⊂ SP ACE(2n ) ⊂ . . . .

X
6= 6= 6= 6=
Kr

aft
E
r
V.

,d
L
tes
P
No
M
re
ctu
CO
Le
 Y
Глава 4

T
i
Моделирование других sk
языков программирования.

I
up
4.1

X
Схема моделирования других языков програм-
Kr

мирования машинами Тьюринга.

aft
E
Пусть для некоторого языка программирования PrL программы и воз-
можные входные/выходные данные удается представить словами неко-
торого конечного (м.б. достаточно большого) алфавита. Естественно так-

r
же предположить, что отображение
V.

,d
L
program, input 7→ output
tes
окажется вычислимой словарной функцией. Тогда по тезису Тьюрин-
га найдется машина Тьюринга UPrL , вычисляющая это отображение.
P

Она будет универсальной для языка PrL, т.е. UPrL (input, program) '
program(input).
No

input
M

program
UPrL :
рабочие ленты
re

Построение универсальной машины, расширенной блоком записи на

ctu

ее "программную"входную ленту исходной PrL-программы, фактически

CO

есть компиляция PrL в язык машин Тьюринга.

31
Le
32 Глава 4. Моделирование других языков.

4.2 Моделирование RAM.

Y
В качестве примера рассмотрим простейший вариант языка BASIC (мо-
дели вычислений такого рода называются RAM, Random Access Mashines,
или машинами с неограниченными регистрами).

• Программа оперирует с конечным набором переменных V0, V1, . . .

типа int (двоичное представление, разрядность заранее не ограни-

T
i
чена). Вход и выход записывается в несколько первых переменных.

sk
• Команды программы пронумерованы и выполняются в порядке ну-
мерации. В языке два вида команд – присваивание (напр., 33:V5<-V3+V1)

I
и условный переход (напр., 125:if V5<0 goto 7).
up
Для удобства обработки текста программы машиной Тьюринга вы-

X
берем следующий “тэговый” вариант синтаксиса:
ПРИСВАИВАНИЕ:
Kr

<LET уникальный_номер> <V номер> выражение </LET>

aft
выражение::= константа
|<V номер>
|<V номер> op <V номер>
E
r
op::= + | - | *
V.

,d
L
УСЛОВНЫЙ ПЕРЕХОД:

<IF уникальный_номер> <V номер> номер </IF>

tes
команда: ее запись:
P

33:V5<-V3+V1 <LET33><V5><V3>+<V1></LET>
No

125:if V5<0 goto 7 <IF125><V5>7</IF>

Соответствующая универсальная машина Тьюринга в качестве сво-
M

ей части имеет “математический процессор” – набор лент и компонент

состояний для реализации операций +,-,* , рабочую ленту для хранения
текущих значений переменных в формате <V номер> значение </V>, а
re

также отдельную рабочую ленту для хранения уникального номера ис-

полняемой команды. Исполнение очередной команды сводится к поиску
ее текста на входной "программной"ленте, произведения мат. вычисле-
ctu

ния, записи его результата в соответствующую переменную и нахожде-

CO

ния номера следующей команды.

Le
4.2. Моделирование RAM. 33

Нетрудно заметить, что время моделирования одного шага оценива-

ется полиномом от текущей зоны, которая, в свою очередь оценивается

Y
линейной функцией от s – максимума длин двоичных записей значений
переменных (максимум – по всему вычислению). Таким образом, для
моделирующей машины

T IM E = O(t · poly(s)), SP ACE = O(s), (4.1)

T
i
где t – количество шагов, а s – максимум длин двоичных записей теку-

sk
щих значений переменных моделируемого вычисления.
Замечание. При добавлении в язык других представляемых слова-

I
ми типов данных и дополнительных встроенных операций (при условии
up
их вычислимости на машинах Тьюринга за полиномиальное время на
линейной зоне) полученные оценки не изменятся. Нетрудно также реа-

X
лизовать этими средствами управляющие конструкции:

IF vi>=0 THEN ... ELSE ... FI Цена – дополнительных 2

Kr

шага.

aft
FOR vi:= vj DOWNTO 0 DO ... DONE Цена: +2 шага к каж-
E
дой итерации, но само количество итераций есть vj +1 и оцен-
ка (4.1) сохранится только в том случае, когда текущее зна-

r
чение переменной vj есть poly(s) (т.е. его длина – O(log s)).
V.

,d
REPEAT ... UNTIL vi>= 0 Цена: +1 шаг к каждой итерации,
L
но для получения оценок времени необходим честный подсчет
числа итераций.
tes
WHILE vi >= 0 DO ... DONE Цена: +2 шага к каждой итера-
ции но для получения оценок времени необходим честный
P

подсчет числа итераций.

No

Замечание. Некоторое неудобство для программирования представ-

M

ляет ограничение, состоящее в фиксированности (для данной програм-

мы) числа используемых переменных. Его легко преодолеть добавлени-
ем в синтаксис ссылок: <REF номер > означает содержимое переменой <V
re

номер’>, где номер’ есть содержимое переменной-указателя <V номер>.

Разрешим использовать ссылки всюду, где могли стоять переменные.
Например, если в переменной V5 хранилось число 31, то команда
ctu
CO

25: REF5 <- 13

Le
34 Глава 4. Моделирование других языков.

приводит к присваиванию V31 <- 13 (если же значение V5 не было опре-

делено заранее, то происходит ошибка). Нетрудно заметить, что в случае

Y
такого расширения оценки (4.1) сохранятся, если взять s = m · l, где m
– количество использованных программой переменных (прямо и косвен-
но), а l – максимум длин двоичных записей их текущих значений.
Эти оценки обычно используют для получения грубых верхних оце-
нок времени, достаточного для решения той или иной задачи на машинах

T
Тьюринга. Выбирают подходящий язык PrL и программируют соответ-

i
ствующий алгоритм на нем, оценивая порядки величин t, s. Для полу-

sk
чения более точных оценок стараются улучшить оценку (4.1) в случае
моделирования специфического алгоритма.

I
up
4.3 Моделирование булевых схем.

X
Булевы схемы – это более простой (не универсальный) язык программи-
Kr

рования того же сорта. Основное отличие состоит в том, что возможные

aft
значения переменных здесь булевы, т.е. 0 или 1. Отсутствует нумерация
команд и условные переходы (нет возможности оперировать с адреса-
E
ми команд и переменных). Программа состоит из последовательности
операторов присваивания

r
V.

,d
L
y <- <op> (x1,...,xk), tes
исполняемых последовательно. При этом фиксирована конечная полная
система булевых функций F (например, {¬, ∨, ∧}) и <op>∈ F . Все пере-
P

менные, встречающиеся только в правых частях операторов присваива-

ния, считаются входными. Некоторые из переменных схемы объявляют-
No

ся выходными. Таким образом, каждая схема вычисляет булеву вектор-

функцию {0, 1}n → {0, 1}m .
M

Другое представление булевых схем – помеченный ориентированный

граф без циклов (DAG). Вершины-источники (без входящих ребер) по-
мечены входными перемеными, а все остальные вершины – символами
re

<op>∈ F При этом в вершину, помеченную n-местной опрерацией, долж-

но входить ровно n ребер. Некоторые из вершин отмечены как стоки
(выходные переменные). Это представление соответствует программам,
ctu

в которых в левых частях операторов присваивания переменные не по-

CO

вторяются.
Le
4.3. Моделирование булевых схем. 35

Представления булевой схемы XOR:

Y
программа DAG
y1 <- ¬x1 x1 x2
y2 <- ¬x2
y3 <- y1 ∧ x2 ¬ ¬

T
y4 <- x1 ∧ y2 ∧ ∧

i
y5 <- y3 ∨ y4
∨

sk
В качестве временной сложности булевой схемы S используют раз-

I
мер схемы size(S) – длину программы (т.е. количество операторов) в
up
первом случае и количество помеченных символами операций вершин –

X
во втором. Легко заметить, что по отношению к временной сложности
эти два представления "эквивалентны"(в программе можно переимено-
вать переменные так, чтобы имена переменных в левых частях операто-
Kr

ров не повторялись, а программа вычисляла ту же функцию с той же

aft
временной сложностью).
E
Схемной сложностью функции f : {0, 1}n → {0, 1}m называется
c(f ) = min{size(S) | S вычисляет f }.

r
Эта характеристика зависит от выбора полной системы F , т.е. c(f ) =
V.

,d
cF (f ), но зависимость не очень существенна: при переходе к другой пол-
L
ной системе схемная сложность функций меняется на множитель O(1).
В дальнейшем полную систему F будем считать фиксированной.
tes
Универсальная для языка булевых схем машина Тьюринга стоится
полностью аналогично случаю RAM, но с соответствующими упрощени-
P

ями (нет необходимости отдельно хранить номер текущей команды, не

надо моделировать IF). Оценка времени работы моделирующей машины
No

Тьюринга в этом случае будет

T IM E = O( (size(S))2 · log size(S) ). (4.2)
M

Она получается аналогично (4.1). Т.к. количество переменных ограниче-

но сверху размером схемы, а на хранение одной переменной достаточно
re

log size(S) + const

клеток ленты (не более log size(S) на номер переменной и const на булево
ctu

значение и разделители), то для хранения текущих значений перемен-

CO

ных уходит s = size(S) · log size(S) клеток ленты.

Le
36 Глава 4. Моделирование других языков.

Моделирование исполнения одного оператора сводится к поиску зна-

чений операндов (O(s) шагов), вычисления значения правой части опе-

Y
ратора (булева операция вычисляется за O(1) шагов) и записи результа-
та в переменную, стоящую в правой части оператора (еще O(s) шагов).
Перемещение головки на "программной"ленте к следующему оператору
дает незначительный вклад O(log size(S)) шагов. Итого, на один опе-
ратор моделируемой программы уходит O(s) шагов, а всего операторов

T
size(S), что и дает требуемую оценку.

i
Замечание. На самом деле логарифмический сомножитель в (4.2)

sk
можно убрать, организовав хранение значений всех переменных без имен
(номеров). Поиск значения переменной номер i в этом случае осуществ-

I
ляется выбором i-того значения от начала. Этот же метод может быть
up
применен в случае BASIC, но не проходит при добавлении ссылок.

X
Kr

aft
E
r
V.

,d
L
tes
P
No
M
re
ctu
CO
Le
CO V.
M Kr

37
up
Часть II
P sk
КЛАССЫ.
Le L i
ctu СЛОЖНОСТНЫЕ
E
re X
No
tes
,d
IT
aft r Y
CO V.
M Kr
up
Le
P L sk
i
ctu E
re X
No
tes
,d
IT
aft r Y
 Y
Глава 5

T
i
Класс P .
sk

I
up
5.1 Определение класса P .

X
Функция f – полиномиального роста, если для некоторых c и n0 выпол-
нено
Kr

f (n) < nc при n > n0 .

aft
Время работы машины Тьюринга M на словах алфавита Σ (подмноже-
E
ство ленточного алфавита) полиномиально, если
TM (n) = max TM (x), где |x| = |x1 | + . . . + |xk |,

r
|x|=n
V.

,d
есть функция полиномиального роста (в частности, такая машина всегда
L
останавливается на словах алфавита Σ; можно также использовать |x| =
max |xi | – получится эквивалентное определение).
tes
Определение 5.1 Класс P в широком смысле состоит из всех то-
P

тальных функций f : (Σ∗ )k → (Σ∗ )l , вычислимых на машинах Тьюрин-

га с полиномиальным временем работы. Класс P в узком (основном)
No

смысле, состоит из всех предикатов L : Σ∗ → {0, 1}, вычислимых на

машинах Тьюринга с полиномиальным временем работы.
M

Замечание. Часто предикаты на множестве Σ∗ отождествляют с их

областями истинности
re

{x ∈ Σ∗ | L(x) = 1}
и называют формальными языками. В этом случае элементы класса P
ctu

(в узком смысле) есть языки, для которых условие “x ∈ L” распознается

CO

за полиномиальное время.

39
Le
40 Глава 5. Класс P .

Замечание. Алфавит Σ в этом определении не фиксирован – в класс

P входят все такие функции и предикаты для всевозможных конечных

Y
алфавитов: [
P = PΣ .
Σ

В то же время для каждого алфавита Σ двоичное кодирование букв по-

рождает естественное вложение PΣ 7→ P{0,1} , поэтому P{0,1} фактически

T
уже содержит в себе все функции и предикаты из P .

i
sk
Замечание. Определение класса P в значительной мере не зависит
от модели вычисления. Если модель вычислений допускает компиляцию
в машины Тьюринга и обратно с полинимиальным замедлением (а тако-

I
вы все реальные языки программирования), то класс P , определенный
up
посредством этой модели совпадает с нашим. В частности, совершенно

X
несущественен выбор варианта машин Тьюринга (сколько каких лент,
головок и т.п.).
Замечание. Имеется устойчивое общественное мнение, что преди-
Kr

каты и функции не из P реально вычислять гораздо труднее, чем пре-

aft
дикаты и функции класса P . Практические задачи, которые лежат в
E
классе P , но требуют для своего решения времени, оцениваемого поли-
номом большой степени, встречаются крайне редко. Обычно приходится

r
сталкиваться с одной из двух реалий: либо задача решается за время –
V.

полином небольшой степени с не слишком большими коэффициентами,

,d
либо она требует экспоненециального времени, причем резкий рост вре-
L
менных затрат начиннается уже на малых длинах входных данных. Эти
различия наглядно проявляются в процессе эксперимента, поэтому факт
tes
принадлежности задачи классу P позволяет прогнозировать реальное
поведение соответствующей программы.
P
No

5.2 Примеры: целочисленная арифметика.

Считаем, что числа представлены в двоичной записи. Тогда операции
M

+, -, *, div, mod (работают “школьные” алгоритмы ), нод(a,b) (алгоритм

Евклида: нод(a, b) = нод(b, a mod b) ) принадлежат классу P .
re

Заметим, что exp(x) = 2x не принадлежит классу P , т.к. длина ре-

зультата уже не полиномиальна как функция от длины x (т.е. от log2 x).
Например, для d = a div b и r = a mod b :
ctu
CO

d:=0;
Le
5.2. Примеры: целочисленная арифметика. 41

WHILE (a >= b) DO // (log a) итераций

x:=1;

Y
WHILE a-x*b >0 DO // (log a) итераций.
z:=x; // Подбираем z -
x:=x*2; // наиб. степень 2 такую,
DONE; // что a=z*b+y и y>=0

T
i
d:=d+z; a:=a-z*b;
DONE
r:=a. sk

I
up
Представим себе реализацию этого алгоритма на описанном выше

X
варианте BASIC’а. Здесь 7 переменных, а в реализации будет 7 + const.
Здесь 10 операторов, а в реализации будет 10 · const. Здесь длины дво-
ичных записей текущих значений переменных не более s = (log a +
Kr

log b) · const и там – тоже. Здесь каждый оператор исполнялся не бо-

aft
лее log2 a раз и там – тоже. В итоге для реализации будет t = C1 · log2 a,
а s = (log a + log b) · C2 . По (4.1) получаем, что при моделировании этого
E
машиной Тьюринга время работы окажется ограниченным полиномом
от n = log a + log b. Но такое значение n и есть длина входных данных,

r
откуда div, mod ∈ P .
V.

,d
Алгоритм Евклида d=нод(a,b):
L
tes
IF b>a THEN x:= a; a:= b; b:= a FI; //делаем a>=b
P

WHILE b>0 DO
x:= a mod b; // (a,b):= (b, a mod b)
No

a:= b;
b:= x
M

DONE;
d:= a.
re

На каждой итерации произведение ab уменьшается по крайней мере

в 2 раза (т.к. a ≥ b + (a mod b) ≥ 2 · (a mod b)), поэтому количество
ctu

итераций не больше log2 ab = log2 a + log2 b, т.е. длины входных данных.

CO

Далее повторяем те же рассуждения про моделирование.

Le
42 Глава 5. Класс P .

5.3 Примеры: арифметика остатков.

Y
Операции +, ∗ в кольцах вычетов ZZm легко вычисляются за пролиноми-
альное время с помощью целочисленной арифметики. Алгоритм Евкли-
да позволяет за полиномиальное время по a и m распознать обратимость
элемента a в кольце ZZm (проверяем условие нод(a, m) = 1). Более тон-
кие факты: функции f (x, n) = x−1 в ZZm (если не существует, то 0) и
exp(x, y, m) = xy mod m также лежат в классе P .

T
i
(xy mod m). Сначала заметим, что при y = 2k это выражение мож-

sk
но вычислить с помощью k итераций оператора x:=x*x mod m. Общий
случай сводится к этому при помощи разложения

I
y = 2k1 + . . . + 2kn , k1 < . . . < kn , n ≤ kn ≤ |y|.
up
Достаточно следующего алгоритма:

exp:=1; z:=1;
WHILE y>0 DO

X
// будет n итераций
Kr

IF (y mod 2 =1) THEN

aft
u:= (x^z) mod m; // z есть степень двойки

FI;
exp:=exp*u
E
z:=z*2;

r
y:=y div 2
V.

,d
DONE.
L
f (x, n) = x−1 в ZZm . Если x – обратимый элемент кольца ZZm , то
tes
(x, m) = 1 и достаточно найти разложение единицы αx + βm = 1 (тогда
x−1 = α mod m). Для поиска такого разложения следует модифици-
P

ровать алгоритм Евклида (нод(x, m)), т.е. реализацию выполняемого в

цикле присваивания
No

r := a mod b ;
(a,b) := (b, r) ;
M

Будем хранить текущие компоненты пары (a, b) в виде целочисленных

линейных комбинаций исходных данных:
re

a = αx + βm, b = γx + δm,
ctu

(в начальный момент α = δ = 1, β = γ = 0). Тогда

CO

r = a − (a div b) · b,
Le
5.4. Примеры: сложение и умножение матриц. 43

что позволяет найти коэффициенты разложения для следующей итера-

ции. Алгоритм заканчивает работу на паре ((x, m), 0) = (1, 0), поэто-

Y
му в результате будет построено требуемое разложение единицы. Каж-
дая итерация увеличится на фиксированное число шагов, но количество
итераций не изменится. Поэтому сохранится прежняя полиномиальная
оценка на время работы.

T
i
5.4 Примеры: сложение и умножение матриц.

sk
Для простоты ограничимся квадратными (n × n) матрицами с элемента-
ми из кольца ZZ2m , представленными двоичными записями с лидирую-

I
щими нулями длины m = const. На вход поступают число n и элементы
up
матриц A,B (записанные подряд через разделитель). Длина входа есть
полином от n, поэтому достаточно построить вычисление, ограниченное

X
по времени другим полиномом от n. Рассмотрим, например, умножение.
Тьюрингово вычисление будет состоять в моделировании соответ-
ствующей программы обсуждавшегося ранее варианта BASIC’а со ссыл-
Kr

ками. Эта программа получает исходные данные в качестве начальных

aft
значений переменных V 0, . . . , V (2n2 ) и должна записать элементы про-
E
изведения матриц в переменные V (2n2 + 1), . . . , V (3n2 ). (Моделирующая
машина Тьюринга должна проделать инициализацию переменных и в

r
конце переписать результат на выходную ленту; очевидную реализацию
V.

,d
этого мы опускаем.)
L
Сама BASIC-программа получается как результат моделирования
стандартного метода перемножения матриц (O(n3 ) итераций)
tes
FOR i=0 TO n-1 DO
FOR j=0 TO n-1 DO
P

FOR k=0 TO n-1 DO

c[i,j]:=c[i,j]+a[i,k]*b[k,j]
No

DONE
DONE
M

DONE

Единственное, что требует разъяснений – реализация массивов (т.е. пе-

re

ременных в индексах) с помощью ссылок. Вместо выражения a[i,k] в

BASIC-программе надо использовать ссылку ref d на значение a[i,k].
Оно хранится в переменной V (i · n + k), поэтому переменной V d надо
ctu

предварительно присвоить значение (i · n + k). Таким образом, оператор

CO

... a[i,k] ... надо переводить так

Le
44 Глава 5. Класс P .

100: Vd <- i * n
101: Vd <- Vd + k

Y
102: ... (ref d) ...

где i, k, n обозначают переменные, хранящие значения i, k, n. Для

остальных двух массивов поступаем аналогично, но учитываем, что со-
ответствующие адреса есть (n2 + k · n + j) и (2 · n2 + i · n + j). В итоге тело
самого внутреннего цикла будет переведено фиксированым (конечным)

T
i
набором операторов присваивания и временная оценка t = O(n3 ) при
переводе всего блока сохранится. Суммарная длина содержимого всех
sk
переменных будет не более s = 3 · n2 · m + const · log n = O(n2 ). Применя-
ем (4.1) и получаем полиномиальную оценку на время соответствущего

I
тьюрингова вычисления.
up

X
5.5 Примеры: связность в графе.
Граф G с множеством вершин {1, . . . , n} задан матрицей смежности M .
Kr

Это симметричная n×n матрица из 0 и 1; mi,j = 1 т. и т.т., когда в графе

aft
есть ребро (i, j). Например,

1 2

E
0 0 1 1

 0 0 0 0 

r
G: M =  1 0 0 1  .

V.

,d
3 4 1 0 1 0
L
Надо по M, i, j выяснить, связаны ли вершины i, j в графе G.
Эта задача легко сводится к вычислению n-ой степени 0,1-матрицы
tes
A = (M + E), если в качестве операций +, · взять булевы операции ∨, ∧
(далеко не самый эффективный метод, но для доказательства принад-
P

лежности классу P работает). Степень матрицы Aq задает отношение

(n)
связности за ≤ q шагов, поэтому для (ai,j ) = An
No

(n)
ai,j = 1 ⇔ i и j связаны в G.
M

Вычислять An можно n-кратным перемножением матриц (см. преды-

дущий пример; использование булевых операций вместо +, · ничего не
re

меняет).
ctu
CO
Le
 Y
Глава 6

T
i
Класс P/P oly. sk

I
up
6.1 Распознавание языков последовательностями
булевых схем.

X
Kr

Напомним, что формальным языком мы назвали произвольное множе-

aft
ство слов данного алфавита. Ограничимся языками L ⊂ {0, 1}∗ . С каж-
дым таким языком можно связать последовательность булевых функций
E
fn (x1 , . . . , xn ), n = 0, 1, . . . такую, что

r
x1 . . . xn ∈ L ⇔ fn (x1 , . . . , xn ) = 1.
V.

,d
L
Схемной сложностью языка L называется функция

cL (n) = c(fn ),
tes
где через c(·) обозначена схемная сложность булевой функции.
P

Пример. Оценить сверху схемную сложность языка, состоящего из

No

всех слов-перевертышей. Схема для fn в этом случае может быть такая:

M

f <- ( x1 <-> xn )

z <- ( x2 <-> x(n-1) )

re

f <- ( f & z )
ctu

z <- ( x3 <-> x(n-2) )

f <- ( f & z )
CO

...

45
Le
46 Глава 6. Класс P/P OLY .

Поэтому cL (n) = O(n).

Следует заметить, что схемная сложность языка является огрублен-

Y
ной сложностной характеристикой – она не учитывает трудоемкость по-
строения самой схемы. Но за счет огрубления становится принципиаль-
но возможным оценивать сложность произвольных языков (а не только
разрешимых, как для машин Тьюринга).
Класс P/P oly определяется как семейство всех таких языков L ⊂

T
{0, 1}∗ , схемная сложность которых есть функция полиномиального ро-

i
ста, т.е.

для некоторых C и n0 .
sk
cL (n) < nC при n > n0

I
Класс P/P oly замкнут относительно операций объединения, пересе-
up
чения и дополнения (проверить) языков.

6.2 Континуальность класса P/P oly.

X
Kr

В отличии от класса P , в класс P/P oly входят не только разрешимые

aft
языки. Мощность класса P/P oly равна континууму. Каждой (не обяза-
E
тельно вычислимой) функции ϕ : N → {0, 1} можно инъективно сопо-
ставить язык L схемной сложности O(1):

r
x1 . . . xn ∈ L ⇔ ϕ(n) = 1.
V.

,d
L
Класс P представляет собой эффективизованную версию класса P/P oly:
если к определению языка L ∈ P/P oly добавить условие вычислимости
tes
за полиномиальное время отображения

булева схема полиномиального размера,
P
s
n 7−→
вычисляющая fn ,
No

то класс таких языков в точности совпадает с P{0,1} .

Для доказательства принадлежности языков L, лежащих в модифи-
M

цированном указанным образом (“равномерном”) классе P/P oly, к клас-

су P{0,1} , достаточно реализовать следующий алгоритм проверки усло-
вия “x ∈ L”:
re

1. По входному слову x = x1 . . . xn найти его длину n.

ctu

2. По n найти булеву схему Sn , правильно проверяющую условие “x ∈

CO

L” на словах длины n.
Le
6.3. Включение P ⊂ P/P OLY . 47

3. Вычислить Sn (x1 , . . . , xn ) и выдать полученный результат в каче-

стве ответа.

Y
Для реализации можно взять композицию машины Тьюринга, вычис-
ляющей отображение s и универсальной машины Тьюринга для языка
булевых схем. Получится машина Тьюринга, которая распознает язык
L за полиномиальное время.
Обратное включение обеспечивает конструкция из доказательства

T
i
теоремы 6.1 (см. ниже), которая на самом деле строит отображение s

6.3
sk
вычислимым за полиномиальное время.

Включение P ⊂ P/P oly.

I
up
Ранее обсуждалось, что с точностью до кодировки исходных данных

X
класс P (в узком смысле) совпадает с P{0,1} (ограничение алфавитом
{0, 1}).
Kr

Теорема 6.1 P{0,1} ⊂ P/P oly.

aft
Доказательство. Пусть L ∈ P . Тогда существует одноленточная ма-
E
шина Тьюринга M , разрешающая L, и полином p(n), ограничивающий
сверху ее время работы на словах достаточно большой длины n. Этот

r
же полином будет ограничивать и зону M . Занумеруем клетки ленты
V.

,d
целыми числами, 0 – где стоит головка в начальный момент, входное
L
слово – в клетках 1, . . . , n, число n – достаточно большое.
Протоколом работы машины Тьюринга M за время T на слове x1 . . . xn
называется прямоугольная таблица следующего вида:
tes
−S 0 1 i S
P

0 #, ∅ . . . #, q1 x1 , ∅ x2 , ∅ ... xn , ∅ . . . #, ∅
No

1 #, ∅ #, ∅
.. ..
. .
M

j #, ∅ Γi,j #, ∅
.. ..
. .
T #, ∅ #, ∅
re

Номера столбцов соответствуют нумерации клеток ленты, номера строк

– шагам вычисления. В клетке (i, j) таблицы записана пара Γi,j =<
ctu

a, q >, где a – содержимое i-той клетки ленты в момент t = j, а q есть со-

CO

ответствующее состояние машины, если в этот момент времени головка

Le
48 Глава 6. Класс P/P OLY .

обозревает клетку i, и ∅ – в противном случае. Ширина таблицы 2 · S + 1

выбирается таким образом, чтобы головка машины в процессе работы

Y
все время находилась внутри куска ленты |i| < S. Если машина оста-
новилась раньше момента T , то последние строки таблицы дублируют
предыдущие. Для этого доказательства возьмем T = S = p(n).
В клетке протокола может стоять произвольная пара < a, q >∈ D,
где D = Σ × (Q ∪ {∅}). Заметим также, что содержимое клетки (i, j + 1)

T
для |i| < S функционально зависит от содержимого трех клеток над ней,

i
Γi−1,j
sk
Γi,j Γi+1,j
Γi,j+1
Γi,j+1 = ϕ(Γi−1,j , Γi,j , Γi+1,j ),

I
а содержимое клеток на верхней, левой и правой границах есть либо
константа < #, ∅ > или < #, q1 >, либо одна из следующих функций от
up
n булевых переменных, представляющих входное слово:

X
< xi , ∅ >= πi (x1 , . . . , xn ).
Kr

Входное слово принадлежит языку L т. и т.т., когда в нижней строке

aft
протокола встречается пара < 1, q0 >.
Добавим к языку программирования булевых схем переменные по
E
конечному множеству D (новый тип данных), константы < #, ∅ >, <
#, q1 >∈ D и дополнительные "встроенные"операции ϕ : D3 → D, πi :

r
{0, 1}n → D, и χ : D → {0, 1}, где
V.

,d
L
χ(< a, q >) = 1 ⇔< a, q >=< 1, q0 > .

В расширенном языке нетрудно написать программу полиномиаль-

tes
ного размера, отвечающую на вопрос “x1 . . . xn ∈ L ?”. Она состоит из
(2 · S + 1) · T операторов присваивания, вычисляющих значения всех пе-
P

ременных Γi,j по слоям сверху вниз и еще 2 · (2 · S + 1) операторов для

вычисления ответа
No

_S
f= χ(Γi,T ).
M

i=−S

Остается промоделировать эту программу программой в исходном

языке булевых схем (без типа D) с сохранением полиномиальной оценки
re

на длину программы. Учитывая конечность множества D, можно вы-

брать число m из условия 2m−1 < |D| ≤ 2m и имитировать каждую
переменную Γ типа D набором из m булевых переменных. Использую-
ctu

щие тип D дополнительные встроенные функции (и константы) можно

CO

заменить на конечные наборы булевых функций, вычисляющие биты

Le
6.3. Включение P ⊂ P/P OLY . 49

результата по битам аргументов. Каждую из последних (их конечное

множество) реализуем булевой схемой (через ¬, ∨, ∧ например). Разме-

Y
ры всех этих схем ограничены некоторой константой d (т.к. их конечное
число). Теперь каждый оператор программы в расширенном языке мож-
но заменить на не более m·d операторов в исходном, производящих то же
преобразование значений переменных, но в их двоичном представлении.
Так как входные и выходные переменые нашей программы уже были

T
булевыми, то это преобразование не изменит вычисляемой программой

i
функции. При этом длина программы возрастет не более, чем в m · d

sk
раз, т.е. останется функцией полиномиального роста.

I
up

X
Kr

aft
E
r
V.

,d
L
tes
P
No
M
re
ctu
CO
Le
 50
CO V.
M Kr
up
Le
P L sk
i
ctu E
re X
Глава 6. Класс P/P OLY .

No
tes
,d
IT
aft r Y
 Y
Глава 7

T
i
Класс N P . sk

I
up
7.1 Определение класса N P .

X
Определение 7.1 Язык L ⊂ Σ∗ принадлежит классу N P , если суще-
ствует предикат R(x, y) ∈ P и полином q(n) = nk такие, что для всех
Kr

x ∈ Σ∗

aft
x ∈ L ⇔ ∃y(|y| < q(|x|) ∧ R(x, y));
E
соответствующий y называется свидетелем принадлежности x ∈ L.

r
V.

,d
Замечание. Класс не изменится, если в определении ограничить-
L
ся предикатами R(x, y) ∈ P с дополнительным условием R(x, y) ⇒ |y| <
q(|x|), т.е. функцию отбраковки "длинных"свидетелей передать предика-
ту R тоже. Тогда распознавание принадлежности языку L можно пред-
tes
ставить как интерактивный процесс, в котором человек пытается "убе-
дить"машину (распознающую предикат R машину Тьюринга) в том, что
P

“x ∈ L”, а машина верифицирует его доводы. На первой входной ленте

No

написано x. Человек пишет на вторую входную ленту потенциального

свидетеля y, а машина вычисляет значение R(x, y) и “соглашается”, ес-
ли результат вычислений есть 1. Слово x принадлежит языку L, если у
M

человека есть принципиальная возможность (но не обязательно эффек-

тивный метод) убедить в этом машину.
re

Замечание. В качестве алфавита для свидетелей достаточно ис-

пользовать {0, 1} (он моделирует остальные). Можно также заменить
условие “|y| < q(|x|)” на “|y| = q(|x|)”, т.к. ϕ(v10k ) = v есть вычис-
ctu

лимая за полиномиальное время биекция множества {y | |y| = m} на

CO

{y | |y| < m} и вместо предиката R(x, y) можно взять R(x, ϕ(y)).

51
Le
52 Глава 7. Класс N P .

Замечание. Каждый язык L ∈ N P разрешим за время 2poly(n) с

помощью перебора всех возможных свидетелей.

Y
Другое эквивалентное определение класса N P использует интерак-
тивную модель вычислений – недетерминированные машины Тьюринга.
Отсюда происходит название класса N P – nondeterministic polynomial.
Недетерминированная машина отличается от детерминированной тем,
что в программе разрешается использовать несколько команд с одина-

T
ковой правой частью “qā → . . .”. Вычисление происходит интерактив-

i
но: человек выбирает одну из возможных в данный момент команд, а

sk
машина проверяет допустимость выбора и производит действия. Таким
образом, для данного входа может быть не одно, а несколько вычисле-
ний. Недетерминированная машина распознает (допускает) язык L за

I
время q(n), если
up

X
x∈L ⇒ на входе x существует вычисление
длины ≤ q(|x|) с результатом 1;
x 6∈ L ⇒ все вычисления на входе x не дают
Kr

результата 1.

aft
И в том и в другом случаях допускается наличие незаканчивающихся
вычислений.
E
Определение 7.2 Язык L принадлежит классу N P , если существует

r
полином q и недетерминированная машина Тьюринга, которая распо-
V.

,d
знает L за время q(n).
L
Лемма 7.3 Определения 7.1 и 7.2 эквивалентны.
tes
Доказательство. (⇒). Считаем, что неравенство в определении 7.1 за-
P

менено на равенство. Процесс угадывания свидетеля y длины q(|x|) мо-

делируется недетерминированным заполнением ленты последовательно-
No

стью из q(|x|) нулей и единиц. Соответствующие команды с одинаковой

левой частью:
qā → . . . 0 . . .
M

qā → . . . 1 . . .
На отдельной рабочей ленте организован счетчик числа повторений,
re

обеспечивающий передачу управления дальше после q(|x|) итераций. По-

сле них недетерминированная машина работает детерминированно и вы-
числяет значение R(x, y).
ctu

(⇐). Легко видеть, что неоднозначность в выборе команд недетер-

CO

минированной машины можно свести к случаю двух команд с данной

Le
7.2. О проблеме P 6= N P . 53

левой частью. Тогда каждое ee вычисление длины ≤ q(|x|) однозначно

определяется 0,1-последовательностью выборов y той же длины (0 озна-

Y
чает, что выбран первый вариант очередной команды, 1 – второй). Рас-
смотрим детерминированную машину M , которая получает y в качестве
дополнительного входа и моделирует интерактивную работу исходной
недетерминированной машины, заменяя человеческое управление чте-
нием очередного бита y. Позаботимся также, чтобы эта машина всегда

T
останавливалась за ≤ q 0 (|x|) шагов (для некоторого полинома q 0 ) и воз-

i
вращала 0 всякий раз, когда исходная не печатала 1 за q(|x|) шагов.

sk
Такая машина M задает требуемый в определении 7.1 предикат R ∈ P ;
в качестве оценки на длину свидетелей подходит полином q.

I
up
7.2 О проблеме P 6= N P .

X
Имеет место включение P ⊂ N P . Для доказательства принадлежности
языка L ∈ P классу N P достаточно взять
Kr

aft
R(x, y) = 1 ⇔ (x ∈ L), q(n) ≡ 1.
E
Вопрос о строгости этого включения, т.е.

r
P 6= N P ?
V.

,d
остается центральной нерешенной проблемой в теории сложности вычис-
L
лений уже более 30 лет. Хотя общественное мнение давно склонилось в
пользу положительного ответа (т.е. неравно) и полезность многих алго-
tes
ритмов основывается на этом (предполагаемом) ответе, строгость вклю-
чения до сих пор не доказана.
P

Имеется некоторая (частичная) аналогия между качественной тео-

рией алгоритмов и количественной, т.е. теорией сложности. Классы P и
No

N P соответсвуют классам разрешимых и перечислимых множеств. Так,

гипотеза о несовпадении классов P и N P есть аналог известной теоремы
M

о существовании перечислимого неразрешимого множества. Другой из-

вестный результат качественной теории – критерий разрешимости Поста
(множество A разрешимо т. и т.т., когда оно и его дополнение Ac пере-
re

числимы). Его аналогом является недоказанное и не опровергнутое (но

сомнительное) равенство P = N P ∩ co-N P , где co-N P состоит из всех
языков L, чье дополнение Lc принадлежит N P . В настоящее время из-
ctu

вестны лишь вытекающие непосредственно из определений (нестрогие)

CO

включения: P ⊂ N P ∩ co-N P ⊂ N P .
Le
54 Глава 7. Класс N P .

NP co-N P

Y
N P ∩ co-N P

T
i
Рис. 7.1: Иерархия классов P , N P , co-N P .

7.3
sk
Примеры задач класса N P .

I
up
Дальнейшие примеры задач из класса N P требуют кодирования рас-
сматриваемых конечных объектов словами подходящего алфавита. Мы

X
предполагаем, что подобное кодирование уже выбрано некоторым ра-
зумным (обычно, очевидным) образом.
Kr

aft
Проблема выполнимости булевых формул (SAT ). Булевы фор-
мулы – это правильные выражения, построенные из булевых переменных
E
p1 , p2 , . . . с помощью булевых связок ∧ (конъюнкция), ∨ (дизъюнкция),
¬ (отрицание) и скобок. Например,

r
V.

,d
(¬(p1 ∧ p2 ) ∨ (¬p1 ∧ p3 )) ∧ p2 .
L
По булевой формуле ϕ(p1 , . . . , pn ) выяснить, существует ли выполняю-
щий ее набор – набор истинностных (0 или 1) значений b1 , . . . , bn , для
tes
которого ϕ(b1 , . . . , bn ) = 1.
Свидетелем правильности ответа “да, выполнима” здесь служит лю-
P

бой выполняющий набор битов (b1 , . . . , bn ). Его размер n не превосходит

длины формулы, т.е. ограничен полиномом первой степени от ее длины.
No

Свидетели имеются у всех выполнимых формул и только у них. Провер-

ка того, что некоторый набор из n битов в самом деле свидетельствует о
M

выполнимости формулы, сводится к вычислению ее истинностного зна-

чения при заданных значениях переменных, что проверяется за полино-
миальное время. Отсюда, SAT ∈ N P .
re

Проблема существования гамильтонова цикла. По графу выяс-

нить, существует ли в нем гамильтонов цикл (замкнутый путь по реб-
ctu

рам графа, проходящий через каждую вершину ровно 1 раз). Свидетель

CO

здесь – гамильтонов цикл.

Le








7.3. Примеры задач класса N P . 55

Y
Задача о клике. Подграф данного графа называется кликой, если он
полный, т.е. каждая пара его вершин соединена ребром. Размер клики

T
– это число ее вершин. По графу выяснить, существует ли в нем клика

i
данного размера d. Свидетель здесь – клика.

sk

I
up

X
Полимино, краевая задача. Полимино – это двухмерное домино.
Костяшки - квадратные, на всех четырех сторонах – пометки (буквы
Kr

фиксированного алфавита). Для каждого варианта игры фиксирован

aft
свой набор типов квадратиков. Краевая задача: на сторонах клетчатого
E
прямоугольника m × n пометки заданы. По краевой задаче и варианту
игры определить, можно ли замостить весь прямоугольник по прави-
лам домино. Для определенности считаем, что крутить костяшки нельзя

r
(фиксирован верх). Свидетель – замощение.
V.

,d
L
Существование целочисленного решения системы линейных нера-
венств. Дана система линейных неравенств с целыми коэффициента-
tes
ми. Выяснить, имеет ли она целочисленное решение. Свидетель – реше-
ние. (Для доказательства принадлежности классу N P нужна полино-
P

миальная оценка на длину свидетеля. Можно показать, что если такая

система имеет целочисленные решения, то длина некоторого из них оце-
No

нивается сверху полиномом от длины системы.)

M

Другие примеры. Следующие задачи лежат в классе N P , но пред-

ставляются более простыми, чем приведенные выше:
re

• Проверить, что данное натуральное число – составное. 1 Свиде-

тель здесь – разложение натурального числа в произведение двух
натуральных сомножителей, каждый из которых больше 1.
ctu

1
CO

В августе 2002 года индийские математики M. Agrawal, N. Kayal и N. Saxena

объявили результат, утверждающий принадлежность этой задачи классу P .
Le
56 Глава 7. Класс N P .

1 7→ 4
5 1 2 7→ 5

Y
3 7→ 2
1 2 3 4 2 3 4 5
4 7→ 3
6 6 5 7→ 1
6 7→ 6

Рис. 7.2: Изоморфизм двух графов.

T
i
sk
• Два графа называются изоморфными, если между их вершина-
ми можно установить взаимно-однозначное соответствие, которое
сохраняет смежность: если две вершины одного графа соединены

I
ребром, то их образы в другом графе – тоже. Само соответствие
up
называется изоморфизмом. Исходными данными задачи является

X
пара графов. Проверить, что данные графы изоморфны. Свиде-
тель здесь – изоморфизм.
Kr

aft
E
r
V.

,d
L
tes
P
No
M
re
ctu
CO
Le
 Y
Глава 8

T
i
Примеры N P -полных задач.
sk

I
up
8.1 Сводимость ≤pm (Карп), N P -полнота.

X
Общий подход к сравнению задач по трудности основан на понятии сво-
димости задач. Он позволяет сравнивать задачи, имеющие форму мас-
Kr

совых проблем (под массовой проблемой понимается семейсто однотип-

aft
ных индивидуальных задач, различающихся лишь значениями исходных
E
данных). Неформально, задача A сводится к задаче B (т.е. не труднее,
“A ≤ B”), если существует метод (протокол), позволяющий решать каж-

r
дую индивидуальную задачу из A, пользуясь решениями индивидуаль-
V.

ных задач из B, поставляемыми "оракулом"извне (по требованию). Есте-

,d
ственно ожидать рефлексивность и транзитивность отношения сводимо-
L
сти ≤. Известно много различных по силе формализаций этого поня-
тия. При изучении сложностных классов в первую очередь используют
tes
“много-однозначную сводимость за полиномиальное время” ≤pm (своди-
мость Карпа).
P

Класс задач ограничивается массовыми проблемами распознавания

языков. Для языка L ⊂ Σ∗ задача распознавания такова:
No

Вход: Вопрос:
M

слово x ∈ Σ∗ x∈L?
re

Определение 8.1 Говорят, что язык L1 ⊂ Σ∗ сводится по Карпу к

языку L2 , т.е. L1 ≤pm L2 , если существует функция f ∈ P такая, что
для всех слов x ∈ Σ∗ выполнено: x ∈ L1 ↔ f (x) ∈ L2 .
ctu
CO

L1 ≡pm L2 ⇔ (L1 ≤pm L2 ) ∧ (L2 ≤pm L1 ).

57
Le
58 Глава 8. Примеры N P -полных задач.

Лемма 8.2 1. Отношение ≤pm рефлексивно и транзитивно.

2. L1 ≤pm L2 , L2 ∈ P ⇒ L1 ∈ P

Y
3. L1 ≤pm L2 , L2 ∈ N P ⇒ L1 ∈ N P

Доказательство. Простое упражнение.

T
Определение 8.3 Язык L называется N P -трудным, если все языки

i
из N P к нему ≤pm -сводятся. N P -трудный язык называется N P -полным,

sk
если он сам также принадлежит классу N P .

I
Замечание. Понятие N P -полноты первоначально возникло в связи
с попытками доказать гипотезу P 6= N P : если это так, то N P -полные
up
языки должны заведомо лежать в разности N P \ P . В настоящее вре-

X
мя известно много примеров N P -полных задач, но ни про одну из них
не удалось доказать (или опровергнуть), что она не лежит в классе P .
Сейчас характеризация задачи как N P -полной (и N P -трудной тоже)
Kr

воспринимается как довод в пользу невозможности ее практического ре-

aft
шения программными средствами в столь общей постановке: написать
E
программу вполне реально, но обеспечить эффективность ее работы на
всех исходных данных не удается. Естественный выход в этой ситуации

r
– сужение задачи, переход к частным случаям, как раз к тем, в которых
V.

программа работает приемлемым образом. (Разработчикам программ-

,d
ных продуктов автор настоятельно рекомендует делать это самостоя-
L
тельно и заблаговременно, не дожидаясь уличения во лжи со стороны
пользователей.)
tes
8.2 N P -полнота проблемы выполнимости буле-
P

вых формул.
No

Теорема 8.4 Проблема выполнимости булевых формул N P -полна.

M

Доказательство. Мы видели, что язык SAT , состоящий из всех запи-

сей (связки ¬, ∧, ∨, скобки, переменная p5 записывается p101) выполни-
re

мых булевых формул приналежит классу N P . Достаточно доказать, что

произвольный язык L ∈ N P сводится к SAT . Общий случай сводится
к следующему: язык L ⊂ {0, 1}∗ задается полиномом p и предикатом
ctu

R ∈ P так
CO

x ∈ L ⇔ ∃y ∈ {0, 1}∗ (|y| = p(|x|) ∧ R(x, y))

Le
8.2. N P -полнота задачи SAT 59

и
|y| =
6 p(|x|) ⇒ ¬R(x, y).

Y
В доказательстве теоремы 6.1 о включении P ⊂ P/P oly мы пред-
ложили метод, который для произвольного фиксированного предиката
из класса P по длине входа n строит булеву схему полиномиального
размера, вычисляющую этот предикат на словах длины n. Этот метод
оказывается эффективным в следующем смысле: само отображение

T
i
n 7→ булева схема Sn

sk
оказывается вычислимым за полиномиальное время (см. его описание).
Применим эту конструкцию к предикату R. Тогда схема Sn+p(n) вы-

I
числяет значение предиката R(x, y) по набору битов его аргументов
up
x1 , . . . , xn , y1 , . . . , yp(n) .

X
Переименовывая рабочие переменные схемы добьемся того, чтобы пе-
ременные в левых частях операторов присваивания не повторялись. По-
сле этого сопоставим схеме булеву формулу ϕ(x1 , . . . , xn , y1 , . . . , yp(n) , z1 , . . . , zk )
Kr

так: каждому оператору присваивания z<-t схемы сопоставим булеву

aft
формулу (z ↔ t), возьмем конъюнкцию их всех и еще переменной, воз-
вращающей значение всей схемы. Переменными формулы ϕ являются
E
все переменные схемы, а длина ϕ также ограничена сверху полиномом
от n.

r
Обозначим через b(v), v ∈ {0, 1}n , набор формул той же длины n с
V.

,d
компонентами
L

w ∧ ¬w , vi = 0,
bi =
w ∨ ¬w , vi = 1,
tes
где w – не встречавшаяся ранее булева переменная. Рассмотрим следу-
ющее отображение f :
P

 
 n := |v| 
No

v ∈ {0, 1}∗ 7→ b := b(v) 7→ ψ(w, y, z) := ϕ(b, y, z).

 
Sn+p(n)
M

Оно вычислимо за полиномиальное время, причем

v ∈ L ⇔ формула ψ выполнима ⇔ f (v) ∈ SAT.

re

Замечание. Если в качестве встроенных функций языка булевых

ctu

схем использовать только одноместные и двухместные операции (напри-

CO

мер, ¬, ∧, ∨), то в каждом операторе присваивания будет не более трех

Le
60 Глава 8. Примеры N P -полных задач.

V
переменных. Тогда конъюнктивные члены формулы ψ = ψj также бу-
дут содержать не более трех переменных каждый. Приведем каждый из

Y
них к КНФ. Это за полиномиальное время даст приведение формулы
ψ к КНФ специального вида, в котором каждый конъюктивный член
содержит не более 3 переменных (так называемые 3-КНФ). Так доказы-
вается

T
Следствие 8.5 Проблема выполнимости 3-КНФ (обозначение: 3SAT )

i
N P -полна.

sk
Замечание. Заметим, что проблемы выполнимости 2-КНФ и ДНФ
принадлежат классу P . Как следствие этого получим, что если P 6= N P ,

I
то задача приведения 3-КНФ к виду ДНФ за полиномиальное время не
up
решается.

8.3 N P -полнота задачи о клике.

X
Kr

Теорема 8.6 Задача о клике N P -полна.

aft
E
Доказательство. Язык CLIQU E ∈ N P состоит из слов, кодирующих
пары (G, d), где G - граф, d натуральное число и в графе G есть пол-
ный подграф из d вершин (клика). Достаточно доказать, что 3SAT ≤pm

r
V.

CLIQU E.

,d
Напомним, что литералом называется булева переменная или ее от-
L
рицание. 3-КНФ ϕ есть конъюнкция скобок, каждая из которых есть
дизъюнкция не более трех литералов:
tes
ϕ = . . . ∧ (li,1 ∨ li,2 ∨ li,3 ) ∧ . . . ∧ (lj,1 ∨ lj,2 ∨ lj,3 ) ∧ . . .
P

Сопоставим ей граф G, вершинами которого будут все вхождения всех

No

литералов в формулу ϕ. Два вхождения соединим ребром, если они на-

ходятся в разных скобрах и не являются "противоположными", т.е. не
есть пара x и ¬x. Граф G будет выглядеть примерно так:
M

. . . x . . . ∧ (¬x ∨ y ∨ ¬z) ∧ . . . ¬x . . .
re

Для каждой клики в графе нетрудно подобрать истинностные зна-

ctu

чения переменных, обращающие все литералы клики в 1. Если при этом

CO

размер клики d равен количеству коъюнктивных членов в формуле, то

Le
8.4. N P -трудность целочисленного ЛП 61

вся формула обратится в 1. Верно и обратное: если для некоторой истин-

ностной оценки переменных ϕ = 1, то в каждом конъюнктивном члене

Y
можно выбрать по литералу так, чтобы получилась клика (надо выби-
рать li,k = 1 по одному из скобки). Т.е. для функции f (ϕ) := код (G, d),
где d количество дизъюнктивных членов ϕ, выполняется
ϕ ∈ 3SAT ⇔ f (ϕ) ∈ CLIQU E.
Сама f вычислима за полиномиальное время, если все кодирования вы-

T
i
браны достаточно естественно (например, когда граф кодируется мат-

sk
рицей смежностей, числа – двоичным представлением, формулы – своей
записью). Заметим, что константа 3 в этом доказательстве не использо-
валась.

I
up

X
8.4 N P -трудность задачи целочисленного линей-
ного программирования.
Kr

Собственно говоря, задача линейного программирования – это задача

aft
поиска экстремума линейного функционала при наличии ограничений,
E
выраженных системой линейных неравенств. Она не является задачей
распознавания языков, поэтому формально нельзя говорить о ее N P -

r
трудности. Но любые методы ее решения также вынуждены распозна-
V.

,d
вать совместность ограничений, поэтому задача линейного программи-
L
рования не менее трудна, чем задача распознавания совместности си-
стем линейных неравенств. В целочисленном случае последняя задача
уже оказывается (после надлежащей кодировки) задачей распознавания
tes
языка, причем N P -полной задачей. В этом смысле мы утверждаем N P -
трудность задачи целочисленного линейного программирования.
P

Теорема 8.7 Задача распознавания разрешимости в целых числах си-

No

стемы линейных неравенств с целыми коэффициентами N P -полна.

Доказательство. Условие выполнимости КНФ можно эквивалентно
M

переписать в виде условия разрешимости в целых числах следующей

системы неравенств. Запишем условие булевозначности для каждой из
переменных:
re

0 ≤ xj ≤ 1,
а каждому конъюнктивному члену (l1 ∨ . . . ∨ lk ) сопоставим неравенство
ctu


xj , если li есть xj ,
CO

p1 + . . . + pk > 0, где pi =
1 − xj , если li есть ¬xj .
Le
62 Глава 8. Примеры N P -полных задач.

T Y
i
sk

I
up

X
Kr

aft
E
r
V.

,d
L
tes
P
No
M
re
ctu
CO
Le
 Y
Глава 9

T
i
Класс BP P .
sk

I
up
9.1 Вероятностные вычисления за полиномиаль-
ное время.

X
Вероятностная машина Тьюринга – это машина Тьюринга с дополни-
Kr

тельной лентой (только для чтения, головка движется только вправо),

aft
имитирующей (физический) датчик случайных чисел. Во всех ее клет-
E
ках заранее записаны 0 или 1, причем предполагается, что это значе-
ния независимых испытаний случайной величины ξ с P rob{ξ = 0} =

r
P rob{ξ = 1} = 1/2. Количество обращений к датчику в процессе вычис-
V.

,d
ления есть величина зоны на этой ленте, в которой побывала головка;
L
содержимое остальных клеток этой ленты не используется. Будем пред-
полагать следующее:
tes
• Вероятностная машина Тьюринга всегда останавливается и в ка-
честве результата выдает 0 или 1.
P

• Время вычисления ограничено полиномом от длины входа. Слу-

No

чайная лента (в таком формализме) входной не является и учиты-

вается при подсчете зоны вычисления. Как следствие, количество
обращений к датчику случайных чисел также ограничено сверху
M

полиномом от длины входа.

• Вероятностная машина Тьюринга M есть модель вычисления за

re

полиномиальное время случайной величины ζx = M (x) с законом

распределения
ctu

0 1
CO

P rob{M (x) = 0} P rob{M (x) = 1}

63
Le
64 Глава 9. Класс BP P .

как функции от входного слова x. Специфической мерой сложно-

сти таких вычислений является количество обращений к датчику

Y
случайных битов QM (x) – максимум числа использованных клеток
дополнительной ленты-датчика, взятый по всем вариантам вычис-
ления на входе x.
• Случайная величина ζx распознает язык L ⊂ Σ∗ с вероятностью
ошибки α(n), если

T
i
x ∈ L ⇒ P rob{ζx = 1} > 1 − α(|x|),

sk
x 6∈ L ⇒ P rob{ζx = 1} ≤ α(|x|).

Определение 9.1 Язык L ⊂ Σ∗ принадлежит классу BP P (от “bounded

I
probabilistic polynomial”), если существует вычислимая за полиномиаль-
up
ное время случайная величина, распознающая L с постоянной вероятно-

X
стью ошибки α(n) = 1/3.

9.2 Частотные распознаватели.

Kr

aft
Оказывается удобным переформулировать определение класса BP P в
E
комбинаторных терминах без использования понятия случайной вели-
чины. Рассмотрим полином q(n), ограничивающий сверху число обра-

r
щений к датчику вероятностной машины M , распознающей язык L с
V.

,d
вероятностью ошибки α(n).
L
Предикат R(x, y)
“|y| = q(|x|) и машина M на входе x c содержимым ленты-
tes
датчика y возвращает 1”
принадлежит классу P , причем
P

|{y | |y| = q(|x|), R(x, y) = 1}|

No

P rob{M (x) = 1} = .
2q(|x|)
Поэтому
M

|{y||y|=q(|x|), R(x,y)=1}|
x∈L ⇒ 2q(|x|)
> 1 − α(|x|),
(9.1)
re

|{y||y|=q(|x|), R(x,y)=1}|
x 6∈ L ⇒ 2q(|x|)
≤ α(|x|).

Тройку (R, q, α), где R ∈ P , q – полином, а α – любая функция, для

ctu

которых выполнено (9.1), условимся называть частотным распознава-

CO

телем языка L. Мы только что установили, что если язык распознается

Le
9.2. Частотные распознаватели. 65

на вероятностной машине Тьюринга с вероятностью ошибки α, то он

обладает частотным распознавателем с той же α. Верно и обратное –

Y
частотный распознаватель легко переделать в вероятностную машину
Тьюринга, которая будет распознавать тот же язык с той же вероятно-
стью ошибки. Поэтому определение 9.1 эквивалентно следующему:

Определение 9.2 Язык L ⊂ Σ∗ принадлежит классу BP P , если он

T
обладает частотным распознавателем (R, q, α) с α(n) = 1/3.

i
sk
Значение константы 1/3 в этих определениях несущественно – класс
не изменится, если вместо нее взять любое число c, 0 < c < 1/2. За счет
увеличения степени полинома q на 1 можно повысить надежность ответа

I
гораздо больше:
up

X
Лемма 9.3 Каждый язык L с частотным распознавателем (R0 , nd√, 1/3)
обладает также √ частотными распознавателями вида (R1 , nd+1 , (2 2/3)n ),
2
(R2 , nd+2 , (2 2/3)n ), . . ..
Kr

aft
Доказательство. Вычисление значения предиката R1 (x, z):
E
1. вычисляем n := |x| и проверяем условие |z| = nd+1 (если не равно,
то результат 0);

r
V.

,d
2. разбиваем слово z на n кусков длины nd каждый, yi := i-тый
L
кусок;

3. R1 (x, z) := M AJORIT Y (R0 (x, y1 ), . . . , R0 (x, yn )), где M AJORIT Y

tes
– булева функция голосования (мнение большинства ее аргумен-
тов).
P

Частота правильного ответа для R1 может быть вычислена, как веро-

No

ятность более половины успехов в серии из n независимых испытаний в

схеме Бернулли с вероятностью
p успеха p √ = 2/3. Она оценивается снизу
M

величиной 1 − λn , где λ = 2 p(1 − p) = 2 2/3.

Конструкция R2 аналогична, но слово z надо разбивать на n2 кусков
длины nd каждый.
re

Замечание. Возможности вероятностного распознавания языков с

ctu

вероятностью ошибки 0 оказываются теми же, что и у обычного де-

CO

терминированного вычисления (т.е. датчик случайных битов ничему не

Le
66 Глава 9. Класс BP P .

помогает). Это совершенно очевидно для формализма частотных рас-

познавателей: для языка L, обладающего частотным распознавателем с

Y
нулевой вероятностью ошибки (R, q, 0), справедливо

x ∈ L ⇔ ∀y|y|=q(|x|) R(x, y) = 1 ⇔ R(x, 0q(|x|) ) = 1,

т.е. L ∈ P .

T
Замечание. То же самое имеет место и для более общего формализ-

i
ма вероятностных вычислений на машинах Тьюринга с дополнительной

sk
лентой-датчиком, отличающегося от приведенного выше отсутствием
полиномиальных ограничений на время вычислений и число обращений
к датчику случайных битов (требование к вычислению всегда заканчи-

I
ваться – остается). В самом деле, если для некоторого x при некотором
up
заполнении ленты-датчика бесконечной в обе стороны последовательно-

X
стью y вероятностная машина M дает неверный ответ, то тот же (невер-
ный) ответ она будет давать при заполнении ленты-датчика любой по-
следовательностью z, совпадающей с y в битах с номерами |i| ≤ SM (x).
Kr

Мера множества таких последовательностей есть 2−2SM (x) > 0. Поэтому

aft
вероятностное вычисление с нулевой вероятностью ошибки должно не
E
давать ошибки ни при каком заполнении ленты-датчика. Это означает,
что вместо случайного заполнения можно всю ленту-датчик заполнить
(алгоритмически) нулями.

r
V.

,d
L
9.3 Включение BP P ⊂ P/P oly.
Мы видели, что каждый язык L ∈ P обладает алгоритмом-распознавателем
tes
специального “схемного” вида:
P

Для выяснения принадлежности входного слова x языку L

сначала по n = |x| за полиномиальное время вычисляется
No

некоторая булева схема Sn от n входных переменных, а затем

ей на вход подаются биты слова x. Результат Sn (x) оказыва-
M

ется правильным ответом на вопрос “x ∈ L ?”.

Языки L ∈ BP P удается распознавать аналогичными, но вероят-

re

ностными “схемными” алгоритмами. Разница состоит в том, что схема в

этом случае имеет дополнительные входные переменные, Sn = Sn (x, y),
значения которых (т.е. y) надо задавать случайно, пользуясь датчиком.
ctu

Тогда, с большой вероятностью, значение Sn (x, y) совпадет с правиль-

CO

ным ответом на вопрос “x ∈ L ?”.

Le
9.3. Включение BP P ⊂ P/P OLY . 67

Построить “схемный” разрешающий алгоритм для языка L ∈ BP P

можно из любого его частотного распознавателя (R, q(n), α(n)). Доста-

Y
точно в качестве Sn (x, y) взять булеву схему, вычисляющую предикат
R(x, y) по битам слов x, |x| = n и y, |y| = q(n). Тогда α(n) будет вероят-
ностью ошибочного ответа.
Следующая теорема показывает, что, в принципе, от ошибки мож-
но избавиться вовсе с помощью хорошего частотного распознавателя и

T
замены датчика случайности на специальный детерминированный вы-

i
бор значений. Эффективный способ “улучшения” частотных распозна-

sk
вателей известен (лемма 9.3), но достаточно работоспособной методики
выбора дополнительных битов нет.

I
Теорема 9.4 BP P ⊂ P/P oly.
up

X
Доказательство. Пусть L ∈ BP P . По лемме √ 9.3 для L существует
2
частотный распознаватель вида (R, q(n), (2 2/3)n ). Обозначим через
Y (x) множество
Kr

{y | |y| = q(|x|) и значение R(x, y) противоположно “x ∈ L”}.

aft
√
E
Доля множества Y (x) среди всех слов y длины q(n) не больше (2 2/3)n
и
2

r
2
(2 2/3)n · 2n < 1 при n > n0 .
V.

,d
Отсюда для каждого n > n0 найдется двоичное слово yn такое, что
L
[
|yn | = q(n), yn 6∈ Y (x).
tes
|x|=n

Для него выполняется

P

|x| = n > n0 ⇒ (x ∈ L ⇔ R(x, yn ) = 1).

No

Пусть n достаточно велико. Так как R ∈ P ⊂ P/P oly, то существует

M

булева схема размера poly(|x| + |y|), вычисляющая предикат R по битам

слова xy. При |y| = q(|x|) размер этой схемы оценивается полиномом от
длины x. Если взять y = yn , где n = |x|, и добавить q(n) + const опе-
re

раторов для вычисления битов слова yn (оно одно для всех x длины n),
то получится схема полиномиального размера, вычисляющая предикат
“x ∈ L” на словах длины n.
ctu
CO
Le
 68
CO V.
M Kr
up
Le
P L sk
i
ctu E
re X
Глава 9. Класс BP P .

No
tes
,d
IT
aft r Y
 Y
Глава 10

T
i
Вероятностный алгоритм sk
распознавания простых

I
up
чисел.

X
Kr

aft
10.1 Сведения из теории чисел.
E
Факт 1 (Следствие из Китайской теоремы об остатках) Пусть n =

r
u · v, (u, v) = 1. Тогда
V.

,d
(ZZn , +, ·) ∼
L
= (ZZu , +, ·) ⊕ (ZZv , +, ·)

и отображение k 7→ (k mod u , k mod v) есть соответствующий

tes
изоморфизм.
P

Факт 2 (Малая теорема Ферма) Если n – простое и не является де-

No

лителем a, то an−1 ≡ 1(mod n).

M

Факт 3 (Тривиальный) Если b2 ≡ 1(mod n), а b 6≡ ±1(mod n), то n –

составное.
re

Доказательство. В кольце ZZn имеем разложение 0 в произведение

ненулевых сомножителей, (b − 1)(b + 1) = b2 − 1 = 0, поэтому ZZn не поле
ctu

и n – составное.
CO

69
Le
70 Глава 10. Распознавание простоты.

10.2 Извлечение корней.

Y
Лемма 10.1 Задача поиска решения уравнения

xk = n, k, n ∈ N,

в натуральных числах разрешима за полиномиальное время.

Доказательство. Решаем это уравнение приближенно методом поло-

T
i
винного деления с точностью 1. Начальное приближение корня – отрезок

sk
[a, b] := [1, n]. При вычислении середины отрезка округляем до целого
числа, т.е. c := [(a + b)/2]. Для выбора очередного приближения (одного
из отрезков [a, c] или [c, b] в зависимости от результата проверки условия

I
“ck < n”) вычисляем ck , пользуясь двоичным разложением числа k:
up
l1 lt
k = 2l1 + . . . + 2lt , ck = c2 · . . . · c2 ,

X
l
а c2 вычисляем последовательным возведением в квадрат. При этом
прерываем вычисление, если текущий результат стал больше n. Полу-
Kr

чится не блее (l1 + . . . + lt + t) = O(log k) операций умножения чисел,

aft
не превосходящих n. Количество итераций, достаточных для получения
E
приближения точности (b−a) = 1 есть O(log n). Итого, O((log k+log n)2 )
операций. Остается проверить, не является ли одно из чисел a, b точным
решением, что можно сделать таким же образом за то же время.

r
Метод легко программируется на языке типа BASIC. Доказатель-
V.

,d
ство завершается стандартным моделированием этого языка машинами
L
Тьюринга.
tes
10.3 Вероятностный алгоритм распознавания про-
P

стых чисел.
No

Вход: натуральное число n > 2.

Для получения правильного ответа с вероятностью ошибки < 2−d
M

повторить следующую последовательность шагов d раз. Если ни разу не

удалось установить, что число n – составное, то считать его простым.
re

1. Проверка n на четность (если четное, то составное).

2. Проверяем, что n не представимо в виде xk для некоторых нату-
ctu

ральных x и k > 1 (достаточно перебрать k = 2, . . . , [log2 n]). Если

CO

представимо, то оно составное.

Le
10.4. Верификация алгоритма. 71

3. Представляем четное число n − 1 в виде 2k · l, где k > 0, а l –

нечетно.

Y
4. Выбираем a случайно из чисел 1, . . . , n − 1.
2
5. Последовательно вычисляем al , a2·l , a2 ·l , . . . , an−1 по модулю n и
ищем такое j < k, что

T
j ·l j+1 ·l
a2 a2

i
6≡ ±1(mod n), ≡ 1(mod n).

sk
Если нашли, то n – составное (Факт 3).

6. Предыдущий шаг закончился вычислением an−1 mod n. Если an−1 6≡

I
1(mod n), то n – составное (Факт 2).
up
10.4 Верификация алгоритма.

X
Kr

Теорема 10.2 Если число n > 2 – простое, то алгоритм установит

aft
это. Если число n составное, то алгоритм установит это с вероят-
ностью, не меньшей, чем 1 − 2−d .
E
Доказательство. Очевидно, что в случае простого n алгоритм никогда

r
не объявит его составным. Неправильный ответ может получиться толь-
V.

,d
ко в случае нечетного составного n = u · v, нод(u, v) = 1. Покажем, что
L
вероятность неправильного ответа в этом случае (т.е. объявления дан-
ного составного числа n простым) при одной итерации шагов 1 – 6 не
превосходит 1/2. Тогда после d итераций получим вероятность ошибки
tes
не более 2−d .
Пусть ≡ означает сравнение по модулю n. Заметим, что если нод(a, n) >
P

1 для выбранного на шаге 4 числа a, то an−1 6≡ 1, т.к. при a = a1 · c,

No

n = n1 · c
an−1 ≡ 1 ⇒ n1 ≡ a1n−1 · cn−1 · n1 ≡ 0.
M

На шаге 6 это будет обнаружено и алгоритм даст правильный ответ. По-

этому достаточно установить, что по крайней мере для половины чисел
из множества
re

G = {a | 1 ≤ a < n, нод(a, n) = 1}
шаги 5, 6 также приведут к правильному ответу (т.е. обнаружат непро-
ctu

стоту n). Заметим, что G состоит в точности из всех обратимых элемен-

CO

тов кольца ZZn , т.е. является мультипликативной группой этого кольца.

Le
72 Глава 10. Распознавание простоты.

Для абелевой группы (H, ·) обозначим

H i = {xi | x ∈ H}.

Y
Тогда H i – ее подгруппа, а отображение x 7→ xi есть гомоморфизм H на
H i . При этом мощность множества {x ∈ H | xi = h} одна и та же для
всех h ∈ H i . Заметим также, что H i ⊃ (H i )2 = H 2i .
Пусть U и V – мультипликативные группы колец вычетов ZZu и ZZv

T
соответственно. Из Факта 1 следует, что G ∼ = U × V посредством отоб-

i
ражения ϕ(x) = (x mod u , x mod v). Рассмотрим убывающие последо-
вательности подгрупп

Gl ⊃ G2·l ⊃ G2
sk 2 ·l
⊃ . . . ⊃ G2
k ·l
= Gn−1 ⊃ {1},

I
2 ·l k ·l
U l ⊃ U 2·l ⊃ U 2 ⊃ . . . ⊃ U2
up
= U n−1 ⊃ {1},

X
2 ·l k ·l
V l ⊃ V 2·l ⊃ V 2 ⊃ ... ⊃ V 2 = V n−1 ⊃ {1},
j j ·l j
ϕ(G2 ·l ) = U 2 × V 2 ·l , j = 0, . . . , k.
Kr

При выборе каких a ∈ G шаги 5, 6 не допускают ошибки, т.е. объяв-

aft
ляют составное число n = u · v таковым? Это происходит, когда a есть
решение одного из уравнений
шаг 5: x2
j ·l
≡ g,
E j
где g ∈ G2 ·l , 0 ≤ j < k, (10.1)

r
g 6≡ ±1, g 2 ≡ 1,
V.

,d
шаг 6: xn−1 ≡ g, где g ∈ Gn−1 , g 6= 1. (10.2)
L
Сам набор уравнений зависит от n.
Случай 1: U n−1 6= {1} или V n−1 6= {1}. Тогда Gn−1 ∼
= U n−1 × V n−1
tes
также содержит элементы, отличные от 1. Семейство множеств
Mg = {x ∈ G | xn−1 = g}, g ∈ Gn−1
P

образует разбиение G на части по |G|/|Gn−1 | элементов каждая. Среди

No

элементов a ∈ G только элементы M1 не удовлетворяют ни одному из

уравнений (10.2). Частей не менее двух. Поэтому не менее половины
M

элеменов G удовлетворяют хотя бы одному из уравнений (10.2). Если на

шаге 4 будет выбран один из них, то на шаге 6 число n будет объявлено
составным (правильный ответ).
re

Случай 2: U n−1 = V n−1 = {1}. Заметим, что U l 6= {1} и V l 6= {1},

так как l – нечетное и −1 принадлежит им обоим (под −1 понимается
ctu

соответствующий вычет по модулю n, т.е. −1 ≡ (n − 1)). Поэтому

CO

s ·l s ·l
j0 = min{s | U 2 =V2 = {1}} − 1 ≥ 0.
Le
10.5. Оценка сложности. 73

Пусть t = 2j0 · l. Множества Gt , U t , V t являются членами рассматрива-

емых последовательностей.

Y
Подслучай 2.1: одно из множеств U t , V t есть {1}. В этом случае
−1 6∈ Gt , т.к. (−1, −1) 6∈ U t × V t (изоморфизм ϕ переводит Gt в U t × V t ,
а ϕ(−1) = (−1, −1) ). Рассуждаем аналогично случаю 1. Рассмотрим
разбиение множества G на равномощные части

Mg = {x ∈ G | xt = g}, g ∈ Gt . (10.3)

T
i
Частей не менее двух и только элемены одной из них (M1 ) не удовле-
sk
творяют ни одному из уравнений (10.1) при j = j0 . Поэтому по крайней
мере для половины элементов a ∈ G верно, что если на шаге 4 будет

I
j j +1
выбран именно , то на шаге 5 обнаружится, что a2 0 ·l 6≡ ±1, a2 0 ·l ≡ 1,
up
и число n будет объявлено составным.
Подслучай 2.2: |U t | > 1, |V t | > 1. Тогда |Gt | = |U t | · |V t | ≥ 4. Это

X
означает, что в разбиении (10.3) частей не менее четырех и только эле-
менты одной или двух из них (M1 и может быть M−1 ) не удовлетворяют
ни одному из уравнений (10.1) при j = j0 . Далее повторяем те же рас-
Kr

aft
суждения.
E
10.5 Оценка сложности.

r
V.

,d
Теорема 10.3 Задача распознавания простых чисел принадлежит клас-
L
су BP P . 1
tes
Доказательство. Оценим временную сложность вероятностного алго-
ритма распознавания простых чисел. Число итераций d считаем фик-
P

сированным. Достаточно показать, что шаги 1–6 моделируются вероят-

ностной машиной Тьюринга за время, оцениваемое сверху полиномом от
No

log n. Это очевидно для всех шагов, кроме шага 4, где требуется вычис-
лить значение случайной величины ξ с распределением
M

P rob{ξ = a} = 1/N, a = 1, . . . , N
re

(при N = n − 1). Вероятностная машина Тьюринга снабжена лентой-

датчиком случайных битов, что позволяет легко моделировать лишь рас-
пределения с двоично-рациональными вероятностями значений. Здесь
ctu

же число N может быть произвольным.

CO

1
См. сноску на стр. 55.
Le
74 Глава 10. Распознавание простоты.

В предыдущем разделе мы показали, что алгоритм на входе n до-

пускает ошибку только тогда, когда выбранное значение a принадлежит

Y
некоторому (определяемому по n) множеству M , причем |M | ≤ N/2.
Отсюда была получена оценка сверху вероятности ошибки (P rob{ξ ∈
M })d ≤ (1/2)d . Если взять любое другое распределение случайной вели-
чины ξ, то оценка

(Вероятность ошибки) ≤ (P rob{ξ ∈ M })d

T
i
сохранится. Поэтому для доказательства теоремы достаточно научить-
sk
ся вычислять на вероятностной машине Тьюринга за время poly(log N )
значение какой-нибудь случайной величины ξ 0 ∈ {1, . . . , N } с P rob{ξ 0 ∈

I
M } ≤ p < 1 (p не зависит от N ), а затем выбрать в алгоритме параметр
up
d из условия pd < 1/3.
Алгоритм вычисления такой случайной величины ξ 0 :

X
Вход: число N . Выбираем число m из условия 2m−1 < N ≤ 2m
и с помощью датчика случайных битов порождаем случайное
Kr

двоичное слово v длины m. Пусть число k таково, что v есть

aft
двоичная запись числа k − 1 (с лидирующими нулями). Если
E
k ≤ N , то результатом объявляем k, а в противном случае –
число 1.

r
Величина ξ 0 принимает значения из множества {1, . . . , N }, причем
V.

,d
вероятность каждого значения не меньше 2−m . Отсюда
L
N −m
P rob{ξ 0 ∈ M } ≤ 1 − ·2 ≤ 3/4.
2
tes
Количество обращение к датчику случайных битов и общее время рабо-
P

ты этого алгоритма есть O(log N ). Если шаг 4 в алгоритме распознава-

ния простых чисел реализовать таким образом, то d можно взять равным
No

4.
M
re
ctu
CO
Le
 Y
Глава 11

T
i
Конечные игры и класс P H.
sk

I
up
11.1 Конечные игры.

X
Играют два игрока (А) и (М). Начальная конфигурация игры задается
входным словом x ∈ {0, 1}∗ . Правила игры специфицируются следую-
Kr

щими параметрами:

aft
• фиксированным (конечным) количеством ходов k и указанием, кто
начинает;
E
r
• полиномом p, задающим длину одного хода как функцию от |x|;
V.

,d
ход – это слово в алфавите {0, 1} длины p(|x|);
L
• предикатом R ∈ P , задающим условие выигрыша (М) при данной
последовательности ходов w1 , b1 , w2 , b2 , . . .,
tes
R = R(x, w1 , b1 , w2 , b2 , . . .).
P

(Количество аргументов фиксировано, оно на единицу больше чис-

ла ходов.)
No

Игроки по очереди обмениваются ходами. Каждый ход – слово длины

M

p(|x|). После завершения партии с помощью предиката R вычисляется,

кто выиграл. Такая игра называется конечной игрой или ограниченным
детерминированным интерактивным протоколом.
re

Совокупность всех вариантов розыгрыша, начинающихся с данной

начальной конфигурации x, удобно представлять себе в виде дерева иг-
ры. Это дерево порядка ветвления 2p(|x|) , вершины которого соответству-
ctu

ют всевозможным “промежуточным” конфигурациям, т.е. состояниям

CO

игры, возникающим после i произвольных ходов, i ≤ k.

75
Le
76




Глава 11. Конечные игры и класс P H.






Y
.. p(|x|)
. 




w1 ···
.. b1 w2
.

T
i
sk ..
.

I
up
Рис. 11.1: Дерево игры.

11.2 Определение класса P H.

X
Kr

Пусть начальная конфигурация x фиксирована. Множество всевозмож-

aft
ных партий конечно, поэтому для одного из игроков обязательно суще-
E
ствует выигрышная стратегия – функция, определяющая его очередной
ход по всем предыдущим ходам так, что если руководствоваться ей при

r
выборе ходов, то игрок обязательно выиграет.
V.

,d
Пример. Если ходов 2 и начинает (A), то выигрышная стратегия
L
F для (М) – это функция, которая по каждому возможному ходу w1
игрока (A) вычисляет ответный ход b1 для игрока (M). Она должна удо-
tes
влетворять условию ∀w|w|=p(|x|) R(x, w, F (w)). Такая функция сущестует,
если
P

∀w|w|=p(|x|) ∃b|b|=p(|x|) R(x, w, b).

Для той же игры выигрышная стратегия для (A) – это функция, кото-
No

рая по пустому слову (игрок (A) ходит первым) вычисляет правильный

первый ход. Она должна удовлетворять условию ∀b|b|=p(|x|) ¬R(x, F ( ), b).
M

Выигрышная стратегия для (A) существует, если

∃w|w|=p(|x|) ∀b|b|=p(|x|) ¬R(x, w, b).
re

Легко видеть, что условия существования этих двух стратегий взаимно

дополняющие.
ctu

Определение 11.1 Язык L ∈ {0, 1}∗ распознается игрой, если условие

CO

“x ∈ L” равносильно “для начальной конфигурации x игрок (М) обла-

Le
11.2. Определение класса P H. 77

дает выигрышной стратегией”. Семейство всех таких языков образует

класс P H.

Y
Замечание. Обозначение для класса P H происходит от термина
полиномиальная иерархия (Polynomial Hierarchy), обсуждаемого в сле-
дующей лекции. Собственно полиномиальная иерархия есть набор слож-
ностных классов, структурирующих класс P H, а элементы L ∈ P H –

T
это все языки, сложность которых может быть измерена с помощью по-

i
линомиальной иерархии.

sk
Интерпретация. Игроки - юный Артур и его учитель Мерлин. Ве-
ликий Мерлин обладает неограниченными вычислительными возможно-
стями, в частности, может вычислять выигрышные стратегии, когда они

I
существуют. Он знает, что x ∈ L и хочет передать это знание Артуру.
up
Возможности Артура меньше – доступные ему вычисления полиноми-

X
ально ограничены по времени. При этом он не вполне доверяет Вели-
ким и хочет получить не только сам факт, но и некотое доступное ему
подтверждение. Но он – Избранный и обычно добивается успеха, если
Kr

только это возможно. За него фактически играет Провидение, которое

aft
не слабее Мерлина. Собственных сил Артуру хватает лишь на то, чтобы
проследить за правильностью присуждения выигрыша после окончания
E
игры. В такой ситуации (пока Провидение не покинуло Артура) в ка-
честве подтверждения Мерлину оказывается достаточным выиграть у

r
Артура в соответствующей игре, хотя на самом деле Артур получает
V.

,d
знание
L
“если он все еще Избранный, то x ∈ L ”
и вынужден вечно сомневаться.
tes
Например, они изучают тактику захвата замков. Начальной конфи-
гурацией игры служит план замка. Предполагается, что способов защи-
P

ты и нападения экспоненциально много. Мерлин имитирует защитников

No

и старается убедить Артура, что замок неприступен. Он расставляет

силы защитников, а Артур предлагает план атаки, после чего разыгры-
вается сражение (за полиномиальное время). Получается двухходовая
M

игра, распознающая предикат “замок x неприступен”.

Замечание. Две игры будем считать эквивалентными, если они рас-
re

познают один и тот же язык. Легко видеть, что за счет добавления од-
ного хода в начале можно преобразовать любую ограниченную игру в
эквивалентную, в которой начинает заданный игрок, например, (М). Со-
ctu

ответствующий предикат выигрыша просто будет зависеть от добавлен-

CO

ного хода фиктивно. Аналогично можно управлять выбором последнего

Le
78 Глава 11. Конечные игры и класс P H.

хода. Можно также при необходимости повысить степень полинома, за-

дающего длину хода, и/или количество ходов, т.к. лишние биты может

Y
отбрасывать “сам” предикат выигрыша.
Замечание. Следующие модификации правил игры легко модели-
руются исходными (за счет модификации предиката выигрыша): (а) дли-
на хода не в точности равна, а не превосходит величины p(|x|); (б) ко-
личество ходов не фиксировано, а зависит от входного слова, но огра-

T
i
ничено сверху константой. Более точно это означает, что если язык L
распознается модифицированной игрой, то существует стандартная ко-
sk
нечная игра, которая также распознает L. Идеи моделирования таковы:

I
(a) Длина хода в соответствующей стандартной игре будет nc+1 , где c
есть степень многочлена p. Ход v = v1 . . . vk ∈ {0, 1}∗ , |v| ≤ p(|x|)
up
модифицированной игры моделируется в стандартной игре ходом

X
v1 v1 . . . vk vk 01 |00 {z
. . . 0} .
Kr

|x|c+1 −2k−2

aft
“Стандартный” предикат выигрыша сначала по своим аргументам
E
восстанавливает последовательность ходов модифицированной иг-
ры, а затем вычисляет значение “модифицированного” предиката

r
выигрыша на этой последовательности.
V.

,d
(б) При такой модификации предикат выигрыша имеет два аргумента
L
– начальную конфигурацию x и последовательность ходов w1 b1 w2 b2 . . .,
записанную одним словом без разделителей. Его значение вычис-
tes
ляется после каждого хода, а не только в конце партии. Оконча-
ние партии происходит, когда значение предиката выигрыша после
P

очередного хода стало 1 или когда число ходов достигло макси-

мального, допустимого для данной игры (k). В соответствующей
No

стандартной игре все партии – по k ходов. “Cтандартный” преди-

кат выигрыша определяется следующим образом:
M

R(x, w1 ) ∨ R(x, w1 b1 ) ∨ R(x, w1 b1 w2 ) ∨ . . . .

| {z }
re

k раз

11.3 Замкнутость относительно ∩, ∪ и (·)c .

ctu
CO

Лемма 11.2 Если L1 , L2 ∈ P H, то L1 ∩ L2 , L1 ∪ L2 , Lc1 ∈ P H.

Le
11.3. Замкнутость относительно ∩, ∪ и (·)C . 79

Доказательство. Случай ∩. Для языков L1 , L2 выберем распознающие

их игры так, чтобы длины ходов в них были одинаковыми, а последний

Y
ход первой делал не тот игрок, который начинает вторую. Последова-
тельность ходов для игры, распознающей L1 ∩ L2 , будет состоять из по-
следовательности ходов первой игры ω1 , которая продолжается последо-
вательностью ходов второй игры – ω2 . В качестве предиката выигрыша
следует взять R1 (x, ω1 ) ∧ R2 (x, ω2 ), где R1 , R2 – предикаты выигрыша

T
первой и второй игр.

i
Случай ∪. Для языков L1 , L2 выберем распознающие их игры так,

sk
чтобы у них совпадали длины и количества ходов, причем в обеих иг-
рах первый ход делал (A). Количество ходов в игре для L1 ∪ L2 будет
на единицу больше, а дополнительный первый ход z будет делать (М).

I
Предикат выигрыша R(x, z, ω) будет
up

X
( (z = 0 . . . 0) ∧ R1 (x, ω) ) ∨ ( (z 6= 0 . . . 0) ∧ R2 (x, ω) ).

Случай дополнения. Достаточно передать право первого хода друго-

му игроку, а в качестве предиката выигрыша взять ¬R1 (x, ω).
Kr

aft
E
r
V.

,d
L
tes
P
No
M
re
ctu
CO
Le
80 Глава 11. Конечные игры и класс P H.

T Y
i
sk

I
up

X
Kr

aft
E
r
V.

,d
L
tes
P
No
M
re
ctu
CO
Le
 Y
Глава 12

T
i
Полиномиальная иерархия.
sk

I
up
12.1 Классы полиномиальной иерархии

X
Условимся писать ∃p z вместо ∃z|z|=p(|x|) и ∀p z вместо ∀z|z|=p(|x|) .
Kr

Определение 12.1 Рассмотрим логическую структуру условия суще-

aft
ствования выигрышных стратегий для (М) в n-ходовой игре (т.е. условия
“x ∈ L” ). Если в игре начинает (М), то оно имеет вид
E
∃p w1 ∀p b1 ∃p w2 . . . R(x, w1 , b1 , w2 , . . .), R ∈ P, (12.1)

r
где количество кванторов равно n. Такие игры (полином p и предикат
V.

,d
R ∈ P – любые) называются Σpn -играми, а соответствующие языки обра-
L
зуют класс полиномиальной иерархии Σpn . Для игры, в которой начинает
(А), соответствующее условие будет
tes
∀p w1 ∃p b1 ∀p w2 . . . R(x, w1 , b1 , w2 , . . .), R∈P (12.2)
с кванторной приставкой длины n. Эти игры называются Πpn -играми, а
P

соответствующие языки составляют класс Πpn .

No

Замечание. Само понятие игры в определении классов полиноми-

альной иерархии формально не является необходимым – класс Σpn состо-
M

ит из всех предикатов вида (12.1), а класс Πpn – вида (12.2), где n есть
длина кванторной приставки. Заметим также, что верхний индекс p в
re

обозначениях классов происходит от слова “polynomial” и не обозначает

конкретный полином. Например, в класс Σpn попадают все предикаты
вида (12.1) для всевозможных полиномов p(n) = nc , c = 1, 2, . . ..
ctu

Замечание. Эквивалентные логические описания этих классов по-

CO

лучатся также в следующих случаях:

81
Le
82 Глава 12. Полиномиальная иерархия.

• если вместо кванторов ∃p , ∀p использовать (всюду или в некоторых

местах) ∃z|z|<p(|x|) , ∀z|z|<p(|x|) ;

Y
• если разрешить в формулах (12.1), (12.2) несколько одноименных
кванторов подряд (в этом случае парамер n есть количество чере-
дований кванторов);

• и то и другое одновременно.

T
i
Замечание. Для доказательства принадлежности языка L классу

sk
полиномиальной иерархии достаточно представить предикат “x ∈ L” в
виде (12.1) или (12.2) не для всех, а только для достаточно длинных слов

I
x, |x| > n0 . Такое “неполное” представление легко переделать в “полное”,
переопределив значение предиката R для коротких слов x следующим
up
образом:

X

1, если |x| ≤ n0 и x ∈ L,
R(x, . . .) :=
0, если |x| ≤ n0 и x 6∈ L.
Kr

12.2 Структурные свойста классов полиномиаль-

aft
ной иерархии.
E
Структурные свойства классов Σpn и Πpn собраны в следующей лемме и

r
отражены на Рис.12.1
V.

,d
L
Лемма 12.2 (Структура P H.)

• Πpn = co-Σpn ;
tes
• Σpn ∪ Πpn ⊂ Σpn+1 ∩ Πpn+1 ;
P

• Σp0 = Πp0 = P ; Σp1 = N P ;

No

S S S
• n (Σpn ∪ Πpn ) = n Σpn = n Πpn = P H.

Доказательство. Непосредственное следствие определений.

M

Замечание. В лемме речь идет про нестрогое включение. Про лю-

re

бую пару классов полиномиальной иерархии (кроме Σp0 = Πp0 ) неизвест-

но, совпадают они или нет. В настоящее время наиболее правдоподобной
представляется гипотеза о невырожденности полиномиальной иерархии,
ctu

утверждающая, что все эти классы различны. Из нее, в частности, вы-

CO

текает, что P 6= N P .
Le
12.2. Структурные свойста. 83

T Y
i
PH

sk

I
.. ..
. .
up
Σp2 Πp2

X
Kr

aft
Σp2 ∩ Πp2
E
r
NP = Σp1 Πp1 = co-N P
V.

,d
L
Σp1 ∩ Πp1 BP P
tes
P
P
No

Рис. 12.1: Структура классов полиномиальной иерархии.

M
re
ctu
CO
Le
 *
+
&

)
-
,
'

!



#
"
/
.

%(
$
84 Глава 12. Полиномиальная иерархия.

12.3 Пример.

Y
Рассмотрим следующий пример использования полиномиальной иерар-
хии для получения (верхней) оценки сложности конкретной задачи.
Задача. Вершины единичного 2n-мерного куба раскрашены в два
цвета – белый и черный. По данной раскраске выяснить, имеется ли в
кубе n-мерная грань, все вершины которой – белые.

T
i
sk

I
up

X
Kr

Координаты вершин единичного куба – числа 0 или 1. Для задания

aft
раскраски уместно использовать булеву формулу ϕ(x1 , . . . , x2n ), для ко-
торой
E
ϕ(x1 , . . . , x2n ) = 1 ⇔ вершина (x1 , . . . , x2n ) – белая.

r
Будем дополнительно предполагать, что все 2n переменных встречаются
V.

,d
в формуле и ее размер не превосходит фиксированного полинома от n.
L
Рассмотрим язык L, состоящий из всех представленных таким обра-
зом раскрасок, для которых белая n-мерная грань существует. Покажем,
tes
что уточненная так задача попадает в класс Σp2 , т.е. что L ∈ Σp2 .
Двухходовая игра класса Σp2 , которая распознает язык L, такова.
P

Своим первым ходом, (M) предлагает систему уравнений

No


 xi1 = a1 ,

.. (12.3)
.
M



xin = an ,

которая, по его мнению, задает белую n-мерную грань. Ответный ход

re

(A) состоит в выборе значений для всех остальных координат xj , j 6=

i1 , . . . , in . После пары ходов вычисляется значение ϕ(x1 , . . . , x2n ). Если
оно равно 1, то выигывает (M); в противном случае выигрывает (A).
ctu

Для (M) единственный способ (стратегия) обеспечить себе гаранти-

CO

рованный выигрыш состоит в указании системы уравнений, которая на

Le
12.4. Включение BP P ⊂ ΣP2 ∩ ΠP2 . 85

самом деле задает белую грань. Это возможно тогда и только тогда,
когда такая грань существует. Таким образом, эта игра действительно

Y
распознает язык L.
Замечание. Следует иметь ввиду, что другие уточнения постанов-
ки задачи могут оказаться неэквивалентными рассмотренной, а потому
иметь совершенно другую сложность. Например, если раскраски пода-
вать на вход распознающему алгоритму в виде списка всех черных вер-

T
шин (вершины задаются своими координатами), то очевидным улучше-

i
нием оценки будет класс N P = Σp1 . Недетеримнированному полиноми-

sk
ально ограниченному по времени допускающему алгоритму достаточно
“угадать” систему уравнений (12.3), задающую белую n-мерную грань,

I
а затем (детерминировано) проверить, что ни одна из вершин списка не
up
принадлежит этой грани. В случае двухходовой игры похожая провер-
ка имитировалась ходом (A), когда фактический перебор осуществляло

X
Провидение, а (A) лишь оглашал самый худший для (M) вариант. Здесь
же перебор заменяется одноразовым просмотром исходных данных, по-
этому проверку может осуществить алгоритм, затратив на это время,
Kr

ограниченное полиномом от их длины. (При аккуратной организации

aft
хранения системы (12.3) можно добиться линейной оценки времени.)
E
12.4 Включение BP P ⊂ Σp2 ∩ Πp2 .

r
V.

,d
Теорема 12.3 BP P ⊂ Σp2 ∩ Πp2 .
L
Сведение. Учитывая дополнительность классов Σp2 и Πp2 достаточно
установить, что для каждого языка L ∈ BP P выполняется L ∈ Σp2 и
tes
Lc ∈ Σp2 . Но так как сам класс BP P замкнут относительно дополнений,
то остается установить следующий факт:
P
No

Теорема 12.4 BP P ⊂ Σp2 .

Доказательство. Пусть язык L ∈ BP P и (R, p, α) – его частотный

M

распознаватель – первый из построенных в лемме 9.3, т.е.

p(n) = nd+1 , α(n) = λn , 0 < λ < 1.

re

Для достаточно длинных слов x надо представить условие “x ∈ L” в

ctu

виде эквивалентного, имеющего форму

CO

∃q w∀q b Q(x, w, b),

Le
86 Глава 12. Полиномиальная иерархия.

где q – некоторый полином, а предикат Q принадлежит классу P . Вместо

этого мы построим условие вида

Y
∃p g1 . . . ∃p gk ∀p g Q0 (x, g1 , . . . , gk , g), Q0 ∈ P,

где величина k есть полином от длины x. Его легко свести к требуемому:

q(n) := k · p(n), w := g1 . . . gk , b := g0 . . . 0, а предикат Q “сам” вычисляет
k и разрезает w и b на нужные куски.

T
i
Обозначим через G = G(x) множество всех двоичных слов длины

sk
p(|x|). Тогда кванторы ∃p и ∀p есть просто кванторы по переменным,
пробегающим G. Введем на G структуру абелевой группы с операцией
+ – поразрядным сложением по модулю 2. Обозначим

I
up
Y = Y (x) = {y ∈ G | R(x, y)}

X
множество всех “свидетелей”, используемых частотным распознавателем
для проверки условия “x ∈ L”. Мы покажем, что при подходящем выборе
параметров искомое представление есть
Kr

aft
k
_
x ∈ L ⇔ (∃g1 ∈ G) . . . (∃gk ∈ G)(∀g ∈ G)
E i=1
(g ∈ gi + Y ). (12.4)

r
Сначала убедимся, что (при условии полиномиальности k) в правой
V.

,d
части (12.4) под кванторами стоит предикат из класса P :
L
k
_ k
_
0
Q (x, g1 , . . . , gk , g) ⇔ (g ∈ gi + Y ) ⇔ R(x, g − gi ).
tes
i=1 i=1
P

Теперь займемся выбором параметров, обеспечивающим верность (12.4)

и полиномиальность k. Правая часть (12.4) эквивалентна условию
No

k
!
[
∃g1 , . . . , gk ∈ G (gi + Y ) = G , (12.5)
M

i=1

утверждающему, что с помощью k сдвигов множества Y можно покрыть

re

всю группу G. Естественно ожидать, что это условие выполнено, если

доля δ = |Y |/|G| достаточно велика, и не выполнено, если мала.
ctu

Лемма 12.5 Если k · δ < 1, то условие (12.5) не выполнено. Если |G| ·

CO

(1 − δ)k < 1, то условие (12.5) выполнено.

Le
12.4. Включение BP P ⊂ ΣP2 ∩ ΠP2 . 87

Доказательство. (Специфика выбора группы не используется.) Легко

видеть, что

Y
[k
(gi + Y ) ≤ k · δ · |G|
i=1
откуда следует первое утверждение.
Для доказательства второго утверждения достаточно установить, что
(при указанных условиях) если в качестве gi взять значения, полученные

T
i
в результате независимых испытаний случайной величины, принимаю-
щей произвольные значения из G с равными вероятностями 1/|G|, то
sk k
[

I
P rob{ (gi + Y ) = G } > 0.
up
i=1

X
Оценим вероятность противоположного события, учитывая, что |gi +
Y | = |Y |, а события “g 6∈ (gi + Y )” для фиксированного g и различных i
независимы:
Kr

 !
k

aft
 _ [ 
P rob g 6∈ (gi + Y ) ≤ |G| · (1 − δ)k < 1.

g∈G i=1
E


r
В нашем случае величина δ зависит от входного слова x и оценива-
V.

,d
ется функцией от его длины n = |x|:
L
x 6∈ L ⇒ δ < λn ⇒ k · δ < k · λn
x ∈ L ⇒ δ > 1 − λn ⇒ |G| · (1 − δ)k < 2p(n) · λk·n
tes
Положим k = p(n). При достаточно больших n будет k · λn < 1 и
P

2p(n) · λk·n < 1. По лемме 12.5 отсюда следует, что эквивалентность (12.4)
справедлива для всех достаточно длинных слов x.
No
M
re
ctu
CO
Le
 88
CO V.
M Kr
up
Le
P L sk
i
ctu E
re X
Глава 12. Полиномиальная иерархия.

No
tes
,d
IT
aft r Y
 Y
Глава 13

T
i
Класс P SP ACE.
sk

I
up
13.1 Класс P SP ACE и игры с полиномиальным
числом ходов.

X
Определение 13.1 Класс P SP ACE состоит из всех языков L ⊂ Σ∗ ,
Kr

распознаваемых на машинах Тьюринга с полиномиальным ограничени-

aft
ем на зону вычисления, т.е. для котороых существует машина Тьюринга
E
M , вычисляющая значения предиката “v ∈ L” на словах v ∈ Σ∗ , причем

r
SM (n) = max SM (v)
|v|=n
V.

,d
есть функция полиномиального роста.
L
Это определение полностью аналогично определению класса P , по-
tes
этому к нему также следует отнести все соответствующие комментарии
из лекции 5. В то же время класс P SP ACE гораздо богаче класса P и,
P

по-видимому, уже содержит в себе большинство практически значимых

вычислительных задач.
No

Класс P SP ACE содержит в себе все рассмотренные ранее сложност-

ные классы (P , N P , BP P , P H) кроме “неравномерного” класса P/P oly.
M

Это вытекает из следующего игрового описания класса P SP ACE.

Оказывается, что все языки из P SP ACE и только они могут быть
описаны конечными играми, в которых число ходов не фиксировано,
re

а задается полиномом от длины начальной конфигурации. Такая игра

описывается двумя полиномами p, q и предикатом выигрыша R(x, ω),
принадлежащим классу P . Как и раньше, x ∈ {0, 1}∗ – начальная кон-
ctu

фигурация, а ω = w1 b1 w2 b2 . . . ∈ {0, 1}∗ – слово, составленное из чере-

CO

дующихся ходов двух игроков (M) и (A). Для данного x длины ходов

89
Le
90 Глава 13. Класс P SP ACE.

одинаковы, |wi | = |bi | = p(|x|), и количество ходов q(|x|) – тоже. (Хотя,

как обсуждалось раньше, эти условия можно ослабить без изменения

Y
класса распознаваемых языков до |wi | = |bi | < p(|x|) и количества хо-
дов < q(|x|).) Для определенности будем считать, что первый ход всегда
делает (M). Язык L ⊂ {0, 1}∗ распознается игрой, если он состоит из
всех начальных конфигураций, для которых у (M) есть выигрышная
стратегия, т.е.

T
x ∈ L ⇔ ∃p w1 ∀p b1 . . . R(x, w1 b1 . . .).

i
| {z }
q(|x|)

sk
Легко видеть, что игры с полиномиальным числом ходов моделируют
ограниченные игры (из определения P H) – им соответствуют предика-

I
ты выигрыша, существенно зависящие только от фиксированного числа
up
начальных ходов. Поэтому все языки из P H распознаются и такими иг-

X
рами. Ниже термин игра будет означать именно игры с полиномиальным
числом шагов (их также называют детерминированными интерактив-
ными протоколами).
Kr

aft
13.2 Моделирование игры.
E
Пусть даны игра (p, q, R) и начальная конфигурация x. Рассмотрим дере-

r
во игры (см. Рис.11.1). Оно состоит из всевозможных q(|x|)-элементных
V.

,d
последовательностей ходов w1 b1 w2 b2 . . . (ходы соответствуют ребрам; реб-
L
ра ориентированы от корня к листьям). Каждый путь ω из корня к ли-
стьям задает некоторую партию. На соответствующем листе запишем ее
результат, т.е. значение R(x, ω).
tes
Как выяснить существование выигрышной стратегии для (M):
P

Все ребра-ходы (M) назовем ∨-ребрами, а все остальные – ∧-ребрами.

No

В вершинах, из которой выходят ∨-ребра, поместим функциональный

элемент OR, а в вершинах, из которой выходят ∧-ребра, поместим AND.
Получим схему из функциональных элементов AND, OR, арности 2p(|x|)
M

каждый. Пометки на листьях (значения предиката R) будем считать

входными и продолжим эту разметку на все вершины дерева согласно
re

схеме. Если в корне получится 1, то у (M) есть выигрышная стратегия;

если 0 – нет.
ctu

Как (M) должен играть, если в корне стоит 1 : Он каждый раз

CO

должен выбирать то ребро, которое ведет в вершину с 1.

Le
13.3. Моделирование на полиномиальной памяти. 91

Прямая реализация этого метода распознавания языков приводит к

экспоненциальным затратам памяти на хранение дерева игры. Но на са-

Y
мом деле можно обойтись и полиномиальной памятью, реализовав вы-
числение булевых пометок обходом дерева "влево-вниз".

13.3 Моделирование на полиномиальной памя-

T
i
ти.
sk
Теорема 13.2 Если язык L распознается игрой с полиномиальным ко-
личеством ходов, то L ∈ P SP ACE.

I
up

X
Доказательство. Достаточно показать, что вычисление значения по-
строенной выше {AN D, OR}-схемы можно реализовать на полиноми-
альной зоне, не распределяя память под всю схему целиком.
Kr

Итак, схема представляет собой корневое дерево высоты q(|x|) c по-

aft
рядком ветвления 2p(|x|) . Вершины одного яруса – одинаковые функцио-
E
нальные элементы (либо все – AN D, либо все – OR), причем AN D и OR
ярусы чередуются, а в корне стоит OR. Входные значения (на листьях)

r
вычисляются на полиномиальной зоне с помощью предиката R, если из-
V.

вестен путь из корня к листу. Предполагаем, что ребра, выходящие из

,d
одной вершины, упорядочены (слева направо).
L
На множестве всех вершин зададим линейный порядок "левее или
ниже": x < y если путь из корня в x есть собственное продолжение пути
tes
из корня в y или есть собственное ответвление от этого пути влево:
P

.. ..
. .
No

y •
↓ или . ↓
M

.. .. ..
. . .
x x y
re

Предлагается последовательно вычислять значения схемы в вершинах

дерева в этом порядке (от левой нижней вершины к корню). При этом
ctu

для вычисления значений в вершинах z > x, достаточно знать значения

CO

в вершине x и всех вершинах y < x, расположенных непосредственно

Le
92 Глава 13. Класс P SP ACE.

ниже одной из вершин на пути из корня к x:

Y
OR

. ↓
2p(|x|) ∼ ••• AND

. ↓ (13.1)
••• OR

. ↓

T
i
••• •

sk
Размер подграфа (13.1 ) остается экспоненциальным за счет групп вер-
шин, обозначенных тремя жирными точками. Но каждая такая группа
расположена на одном ярусе, поэтому в значения схемы во всех верши-

I
нах z > x войдет AN D(• • •) или OR(• • •) в зависимости от четности
up
номера яруса. Таким образом, в каждый момент времени достаточно

X
хранить подграф полиномиального размера:
OR
Kr

. ↓

aft
OR(• • •) AND

. ↓
AN D(• • •)
E OR

. ↓

r
OR(• • •) •
V.

,d
L
13.4 Игровая характеризация класса P SP ACE.
tes
Теорема 13.3 Каждый язык L ∈ P SP ACE распознается некоторой
P

игрой с полиномиальным числом ходов.

No

Доказательство. Пусть машина Тьюринга M распознает язык L на

зоне, ограниченной полиномом p. По теореме 2.1 ее время работы можно
M

оценить сверху функцией 2q(n) , где q некоторый полином. Для данного

входного слова x рассмотрим последовательность мгновенных конфигу-
раций C(t), t = 0, . . . , 2q(|x|) , составляющих вычисление M на входе x.
re

C(t) есть содержимое лент, положение головок и состояние машины по-

сле t шагов вычисления; если к моменту t вычисление уже закончилось,
то полагаем C(t) := C(t − 1). По входу x однозначно восстанавливается
ctu

начальная конфигурация C(0). Будем предполагать, что заключитель-

CO

ная конфигурация с ответом “да” также стандартизована (рабочие ленты

Le
13.4. Игровая характеризация класса P SP ACE. 93

очищены, на выходной — ответ 1, головки — в стандартных позициях),

так что ее вид можно восстановить по x не проводя всех вычислений.

Y
Пусть next(C) обозначает следующую за C конфигурацию.

Игра для распознавания принадлежности x ∈ L. Игрок (M) ста-

рается убедить (A), что он обладает правильной последовательностью
конфигураций вычисления M (x) и что это вычисление дает ответ "да".

T
Они совместно пересчитывают значения двух числовых переменных l и

i
r. В начальный момент l = 0, r = 2q(|x|) , Cl := C(0), Cr := стандартная

sk
заключительная конфигурация с ответом “да”.
• Ход (M) – пара (Ct , t), причем он утверждает, что (M.1): t = (r+l)/2

I
(легко проверить) и что (M.2): Ct = C(t), чего (A) непосредственно
up
проверить не может.

X
• Ход (A) состоит в выборе варианта пересчета: l := t или r := t
(выбирается одна из половин отрезка).
Kr

• Игра останавливается после q(|x|) пар шагов. При честной игре в

aft
конце получается r = l + 1.
E
• Предикат выигрыша: Когда одного из игроков удается уличить в
обмане (если нарушено (M.1) или допущена ошибка в пересчете

r
l, r), то нарушивший первым – проиграл. Если то, что (M) выдает
V.

,d
в конце игры за C(l) и C(l + 1) (т.е. Cl и Cr ) в самом деле не
есть 2 последовательные конфигурации машины Тьюринга M , то
L
выиграл (A). В остальных случаях выиграл (M).
tes
Докажем, что эта игра в самом деле распознает язык L. В случае
x ∈ L выигрыш (M) обеспечен тривиальной стратегией – ему надо просто
P

играть честно.
Разберем случай x 6∈ L. Тогда "правильной"допускающей последова-
No

тельности конфигураций не существует и (M) вынужден обманывать.

До первого хода уже определены две пары (Cl , l) и (Cr , r): с l =
0, r = 2q(|x|) ; конфигурация Cl – известная всем начальная, а Cr – та
M

допускающая заключительная конфигурация, возможность получения

которой в результате вычисления M (x) утверждает (M). При этом на
re

самом деле выполнено условие

Cl = C(l) ∧ Cr 6= C(r).
ctu

Если (M) не нарушит правила, то (A) своим ходом может добиться

CO

сохранения этого условия:

Le
94 Глава 13. Класс P SP ACE.

1. Если (M) нарушит правила, т.е. t 6= (l + r)/2, то (A) уже выиграл.

Y
2. Пусть (M) выберет Ct так, что за t−l шагов машина M не преводит
Cl в Ct . Тогда (A) следует выбрать левую половину, т.е. присваи-
вание r := t.

3. Пусть (M) выберет Ct так, что за t − l шагов машина M преводит

Cl в Ct . Тогда (A) следует выбрать правую половину, т.е. присваи-

T
вание l := t.

i
sk
Если досрочного выигрыша не произошло, то условие справедливо и
в конечный момент, когда r = l + 1. По правилам игры (A) в этом случае
также выигрывает.

I
up

X
Kr

aft
E
r
V.

,d
L
tes
P
No
M
re
ctu
CO
Le
 Y
Глава 14

T
i
Полные задачи для класса sk
P SP ACE и классов

I
up
полиномиальной иерархии.

X
Kr

aft
Легко видеть, что класс P SP ACE и каждый класс полиномиальной
иерархии “замкнут вниз” относительно сводимости ≤pm : если C – один
E
из них, то для любых двух языков L1 , L2 выполняется условие

r
L1 ≤pm L2 , L2 ∈ C ⇒ L1 ∈ C.
V.

,d
L
По аналогии с понятием N P -полных задач определим Σpn − и Πpn -полные
задачи как наибольшие (по отношению ≤pm ) элементы соответствующих
классов. Ниже мы приводим типовые примеры таких задач.
tes
P

14.1 Квантифицированные булевы формулы

No

Определение 14.1 Квантифицированной булевой формулой называет-

ся формула вида
M

Q1 x1 . . . Qk xk ϕ, (14.1)

где ϕ – булева формула, Qi xi , i = 1, . . . , k – кванторы существования или

re

всеобщности по булевым переменным xi . Квантифицированная формула

называется Σn -формулой (Πn -формулой), если она начинается с кванто-
ра ∃ (соответственно ∀) и имеет n − 1 чередований кванторов. Кванти-
ctu

фицированная булева формула (14.1) замкнута, если все переменные ее

CO

бескванторной части ϕ лежат среди x1 , . . . , xn .

95
Le
96 Глава 14. ΣPN -, ΠPN - и P SP ACE-полные задачи.

Примеры.

Y
• Формула ∀x∃y (x ∨ y) является истинной замкнутой квантифици-
рованной булевой формулой.

• Формула ∃x (x ∧ ¬x) является ложной замкнутой квантифициро-

ванной булевой формулой.

T
i
• Формула ∃x (x ∧ ¬y) является незамкнутой квантифицированной

sk
булевой формулой, истинностное значение которой зависит от ис-
тинностного значения переменной y.

I
Заметим, что
up

X
∃xϕ(x) ⇔ ϕ(0) ∨ ϕ(1), ∀xϕ(x) ⇔ ϕ(0) ∧ ϕ(1),

поэтому введение булевых кванторов в пропозициональный язык не из-

Kr

меняет выразительных возможностей, но позволяет записывать некото-

aft
рые утверждения существенно короче.
E
Лемма 14.2 Каждая булева функция f (x1 , . . . , xn ) схемной сложно-

r
сти c(f ) может быть (за полиномиальное время) представлена кван-
V.

,d
тифицированной булевой формулой длины O(c(f )) в каждом из видов
L
Σ1 и Π1 . tes
Доказательство. Пусть булева схема для вычисления f размера c(f ) =
k + 1 есть
P

z1 <- t1;
No

...
zk <- tk;
M

y <- t.

Тогда представляющие f формулы таковы:

re

Σ1 -вид: ∃z1 . . . ∃zk ((z1 ↔ t1) ∧ . . . ∧ (zk ↔ tk) ∧ t) ,

ctu

Π1 -вид: ∀z1 . . . ∀zk ((z1 ↔ t1) ∧ . . . ∧ (zk ↔ tk) → t) .

CO
Le
14.2. Полные задачи для классов P H. 97

14.2 Полные задачи для классов полиномиаль-

ной иерархии.

Y
Теорема 14.3 Пусть n ≥ 1. Задача распознавания истинности за-
мкнутых квантифицированных булевых Σn -формул Σpn -полна. Анало-
гичная задача для Πn -формул Πpn -полна.

T
i
Замечание. Мы предполагаем фиксированным побуквенное коди-
рование формул словами в алфавите {0, 1}. Задачи распознавания ис-
sk
тинности формул указанных видов формализуются как задачи распо-
знавания языков, состоящих из кодов формул. Двоичный код формулы

I
F ниже обозначается через “F ”.
up
Доказательство. Сначала проверим, что эти задачи лежат в соответ-
ствующих классах. Пусть дана квантифицированная булева формула F

X
вида (14.1). Заменим в ней каждый блок одноименных булевых кванто-
ров на один квантор по двоичным словам длины m, равной максимуму
количества кванторов в таких блоках. Например,
Kr

aft
F = ∀x1 ∀x2 ∃y1 ∀z1 ∀z1 ϕ(x1 , x2 , y1 , z1 , z2 )
| {z } |{z} | {z }
E
преобразуется в

r
V.

F 0 = ∀x|x|=2 ∃y|y|=2 ∀z|z|=2 ϕ(π1 (x), π2 (x), π1 (y), π1 (z), π2 (z)),

,d
L
где πi – функции “i-тый бит слова”. Теперь заметим, что истинностное
значение выражения под кванторами
tes
(а) не изменится при удлинении слов x, y, z дописыванием справа про-
P

извольных битов до длины n = |F |,

No

(б) может быть вычислено за полиномиальное время по формуле F и

словам x, y, z, т.е.
M

(F – истинна) ⇔ ∀p x∃p y∀p z R(“F ”, x, y, z),

где полином p(n) = n, а R – соответствующий предикат из класса

re

P.

Разумеется, то же самое проходит с любой квантифицированной фор-

ctu

мулой. При этом если F есть Σn (Πn ) -формула, то соответствующая

CO

правая часть будет Σpn (Πpn ) -предикатом.

Le
98 Глава 14. ΣPN -, ΠPN - и P SP ACE-полные задачи.

Теперь покажем, что произвольный язык L ∈ Σpn будет ≤pm -сводиться

к задаче распознавания истинности квантифицированных булевых Σn -

Y
формул. (Случай с Πpn полностью аналогичен.) Пусть

x ∈ L ⇔ ∃p w∀p b . . . R(x, w, b, . . .), (14.2)

где p - полином, а R ∈ P . По доказанной ранее теореме 6.1 P ⊂ P/P oly,

откуда схемная сложность булевой функции f , вычисляющей истин-

T
ностное значение предиката R(x, w, b, . . .) по битам его аргументов, есть

i
функция полиномиального роста. Более того, доказательство теоремы

sk
6.1 предлагало прямую (полиномиальную по времени) конструкцию по-
строения соответствующей схемы Sf по числу m = |x| + |w| + |w| + . . .,

I
которое, в свою очередь, легко восстановить по |x|.
up
Применим лемму 14.2 к схеме Sf и получим представление булевой
функции f квантифицированной булевой Σ1 или Π1 -формулой Ff . При-

X
чем выберем то из них, в котором кванторы совпадают с самым правым
квантором в (14.2). Тогда
Kr

x ∈ L ⇔ ∃w1 . . . ∃wp(|x|) ∀b1 . . . ∀bp(|x|) . . . Ff ,

aft
| {z }
F
E
где формула F справа есть квантифицированная булева Σn -формула
(новых чередований кванторов не добавилось), а отображение

r
V.

,d
x 7→ |x| 7→ m 7→ Sf 7→ Ff 7→ F
L
( т.е. сводящая функция) вычислимо за полиномиальное время.
tes
P

14.3 Пример P SP ACE-полной задачи.

No

Класс P SP ACE также содержит наибольшие элементы – P SP ACE-

полные задачи. К ним относится задача распознавания истинности за-
мкнутых квантифицированных булевых формул. Она представлена язы-
M

ком TQBF, состоящим из (кодов) всех истинных замкнутых квантифи-

цированных булевых формул
re

Q1 x1 . . . Qn xn ϕ(x1 , . . . xn ),
ctu

(Qi xi – квантор ∀ или ∃ по булевой переменной xi ).

CO

Лемма 14.4 TQBF∈ P SP ACE.

Le
14.3. Пример P SP ACE-полной задачи. 99

Доказательство. Определение истинности квантифицированной фор-

мулы F в предваренном виде легко представить игрой. Добавлением

Y
фиктивного квантора ∃ слева можно свести общий случай к

F = ∃x11 . . . ∃xk1 ∀y11 . . . ∀y1l ∃ . . . ϕ.

(M) играет за квантор существования, (A) – за квантор всеобщности.

T
Они оба делают ходы длины |F |:

i
sk w1 = w11 w12 . . .
b1 = b11 b21 . . .
w2 = w21 w22 . . .

I
...
up
Количество ходов можно также взять |F |; оно мажорирует число чере-
дований кванторов в формуле. Предикат выигрыша есть

X
R(‘F ’, w1 , b1 , w2 , . . .) ⇔ ϕ[w11 /x11 , . . . , b11 /y11 , . . .]
Kr

aft
(вместо переменных подставляются первые биты соответствующих хо-
E
дов игроков). Истинность F эквивалентна условию существования вы-
игрышной стратегии для (M).

r
V.

,d
L
Теорема 14.5 Язык TQBF является P SP ACE-полным.
tes
Доказательство. Докажем, что произвольный язык L ∈ P SP ACE
≤pm -сводится к TQBF. Рассморим игру с полиномиальным числом хо-
P

дов, распознающую L:
No

x ∈ L ⇔ ∃p w1 ∀p b1 . . . R(x, w1 b1 . . .),
| {z }
q(|x|)
M

где p, q – полиномы, а R ∈ P . Заменим кванторы по словам на блоки

кванторов по булевым переменным, а предикат R – на вычисляющую
re

его булеву схему полиномиального размера:

x∈L ⇔
ctu

p(|x|) 1 p(|x|)
∃w1 . . . ∃w1 ∀b . . . ∀b1 . . . (S(x, w1 , b1 . . .) = 1).
| 1 {z 1
CO

}
p(|x|)·q(|x|)
Le
100 Глава 14. ΣPN -, ΠPN - и P SP ACE-полные задачи.

Условие S(x, w1 , b1 . . .) = 1 заменим эквивалентной квантифицирован-

ной булевой Σ1 -формулой G полиномиальной длины (по лемме 14.2).

Y
Получим квантифицированную булеву формулу
p(|x|) p(|x|)
F (x) = ∃w11 . . . ∃w1 ∀b11 . . . ∀b1 . . . G,

для которой
v ∈ L ⇔ F (v) ∈ TQBF.

T
i
Все преобразования v 7→ F (v) сами могут быть проведены за поли-

sk
номиальное время, что и доказывает сводимость L ≤pm P SP ACE.

I
up

X
Kr

aft
E
r
V.

,d
L
tes
P
No
M
re
ctu
CO
Le
 Y
Литература

T
i
sk
[1] А. Ахо, Дж. Хопкрофт, Дж. Ульман Построение и анализ вычисли-
тельных алгоритмов. М.: Мир, 1979.

I
up
[2] М. Гэри, Д. Джонсон Вычислительные машины и труднорешаемые
задачи. М.: Мир, 1982.

X
[3] А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисле-
ния. М.: МЦНМО, ЧеРо, 1999.
Kr

aft
[4] Дж. Сэвидж. Сложность вычислений. М.: Изд-во “Факториал”, 1998.

[5] P. Gacs, L. Lovasz.

E
Complexity of Algorithms. 1999.
http://www.cs.yale.edu/HTML/YALE/CS/HyPlans/lovasz/complex.ps

r
[6] J. van Leeuwen, ed. Handbook of Theoretical Computer Science. Volume
V.

,d
A. Algorithms and Complexity. Amsterdam et al.: Elsevier / Cambridge,
L
MA: MIT Press, 1990.
tes
[7] M. Sipser. Introduction to the Theory of Computation. Boston: PWS
Publishing Company, 1997.
P
No
M
re
ctu
CO

101
Le