Иерархия сложностных классов

Разбить на страницы

Показывать лекцию целиком

Иерархия сложностных классов

Напомним, что мы отождествляем языки и предикаты, как описано в лекции 1. В частности, запись $$x\in L$$ означает $$L(x)=1$$.

Определение 4.1. Пусть $$\mathrm A$$ — некоторый класс языков. Класс дополнений $$\text{co-}\mathrm A$$ составляют дополнения ко всем языкам из $$\mathrm A$$. Формально$$L\in\mathrm A \:\Longleftrightarrow\: (\cb^*\setminus L)\in \text{co-}\mathrm A.$$

Непосредственно из определений классов $$P, BPP, PSPACE$$ следует, что $$\P=\text{co-}\P$$, $$\BPP=\text{co-}\BPP$$, $$\PSPACE=\text{co-}\PSPACE$$.

Игры, в которые играют машины.

Рассмотрим игру, в которую играют два игрока, будем их называть белые (Б) и черные (Ч). Игрокам сообщается некоторое слово $$x$$, и они делают ходы по очереди ( $$w_1$$ — первый ход белых, $$b_1$$ — первый ход черных и т.д.). Каждый ход может быть описан словом длины $$p(|x|)$$, где $$p(\cdot)$$ — некоторый полином. Игра завершается после некоторого, заранее заданного, числа ходов. На самом деле правило завершения игры может быть и сложнее. Если есть верхняя оценка на число ходов, то можно всегда дополнить число ходов до этой оценки, никак не учитывая дополнительные ходы при подведении результата игры. Результат игры описывается некоторым предикатом $$W(x,w_1,b_1,\dots)\in\P$$, истинность которого означает, что выиграли белые (ничьих не бывает, так что ложность $$W$$ означает, что выиграли черные). Предикат $$W$$ зависит от исходного слова и ходов, сделанных игроками: $$w_1,\dots$$ — белыми, $$b_1,\dots$$ — черными. Поскольку $$\P$$ замкнут относительно дополнений, предикат $$B(\cdot)=\neg W(\cdot)$$, утверждающий выигрыш черных, также принадлежит $$\P$$.

Отсутствие ничьих и конечность числа ходов гарантируют при заданном $$x$$ существование выигрышной стратегии либо для белых, либо для черных. (Формальное доказательство легко получается индукцией по числу ходов.) Поэтому каждой игре можно сопоставить два взаимно дополнительных множества$$\begin{align*} L_w= \{x:\text{Б имеет выигрышную стратегию}\},\\ L_b= \{x:\text{Ч имеет выигрышную стратегию}\}. \end{align*}$$ Многие сложностные классы можно определить как множества $$L_w$$ (или $$L_b$$ ), соответствующие тем или иным видам игр. Например, получаем следующие классы.

$$P$$: множества $$L_w$$ (как и $$L_b$$, впрочем) для игр, в которых никто не делает ходов.

$$NP$$: множества $$L_w$$ для игр, в которых белые делают 1 ход. Другими словами, это множества вида$$\{x: \exists\,w_1\: W(x,w_1)\}.$$

$$co-NP$$: множества $$L_b$$ для игр, в которых белые делают 1 ход. Другими словами, это множества вида$$\{x: \forall\, w_1\: B(x,w_1)\}.$$

$$\Sigma_2$$: множества $$L_w$$ для игр из 2 ходов: 1 ход белых, 1 ход черных. Другими словами, это множества вида$$\{x:\exists\, w_1\:\forall\, b_1\: W(x,w_1,b_1)\}.$$ Словами это можно сказать так: есть такой ход белых, что, как бы ни сыграли черные, белые выигрывают.

$$\Pi_2$$: множества $$L_b$$ для игр из 2 ходов. Другими словами, это множества вида$$\{x:\forall\, w_1\:\exists\, b_1\: B(x,w_1,b_1)\}$$

$$\dots$$

$$\Sigma_{k}$$: множества $$L_w$$ для игр из $$k$$ ходов (в зависимости от четности $$k$$ последними ходят либо черные, либо белые). Другими словами, это множества вида$$\{x:\exists\, w_1\:\forall\, b_1\:\dots\:\mathsf{Q}_k\, y_k\: W(x,w_1,b_1,\dots)\}$$ (если $$k$$ четное, то $$\mathsf{Q}_k=\forall$$, $$y_k=b_{k/2}$$, если $$k$$ нечетное, то $$\mathsf{Q}_k=\exists$$, $$y_k=w_{(k+1)/2}$$ ).

$$\Pi_{k}$$: множества $$L_b$$ для игр из $$k$$ ходов (в зависимости от четности $$k$$ последними ходят либо черные, либо белые). Другими словами, это множества вида$$\{x:\forall\, w_1\:\exists\, b_1\:\dots\:\mathsf{Q}_k\, y_k\: B(x,w_1,b_1,\dots)\}$$ (если $$k$$ четное, то $$\mathsf{Q}_k=\exists$$, $$y_k=b_{k/2}$$, если $$k$$ нечетное, то $$\mathsf{Q}_k=\forall$$, $$y_k=w_{(k+1)/2}$$ ).

$$\dots$$

Классы $$\Sigma_k$$ и $$\Pi_k$$ взаимно дополнительны: $$\Sigma_k=\text{co-}\Pi_k$$, $$\Pi_k=\text{co-}\Sigma_k$$.

Теорема 4.1 (Лаутеман [35]). $$\BPP\subset\Sigma_2\cap\Pi_2$$.

Доказательство. Поскольку класс BPP замкнут относительно дополнений, достаточно показать, что $$\BPP\subset\Sigma_2$$.

Для этого нужно научиться формулировать свойство "множество содержит много элементов" с использованием кванторов существования и всеобщности. Мы сделаем это, предполагая, что рассматриваются подмножества некоторой конечной группы. Пусть $$G$$ — группа, а $$X$$ — подмножество $$G$$. Свойство, которым мы будем отличать большие множества от малых, состоит в том, что некоторым количеством сдвигов множества $$X$$ можно покрыть всю группу$$\exists\, g_1,\dots,g_k: \bigcup_i g_iX=G.$$

Чтобы выбрать подходящее значение $$k$$, нужно найти случаи, когда (4.1) заведомо выполняется, и когда заведомо не выполняется.

Если$$k|X|<|G|,$$ условие (4.1) заведомо ложно.

Условие (4.1) заведомо истинно, если для случайных независимых $$g_1,\dots, g_k$$ вероятность события $$\bigcup_i g_iX\double=G$$ больше 0. Другими словами, $$\Prob[G\setminus\big( \bigcup_i g_iX\big)\ne\emptyset]<1$$. Вероятность того, что случайный сдвиг $$X$$ не покрывает (не содержит) некоторый фиксированный элемент, равна по очевидным причинам $$1-|X|/|G|$$. Вероятность того, что $$k$$ случайных сдвигов не покрывают фиксированный элемент, равна $$(1-|X|/|G|)^k$$ (покрытия разными сдвигами — независимые события). Поскольку покрывается $$|G|$$ элементов, вероятность события $$\Prob[G\setminus\big( \bigcup_i g_iX\big)\ne\emptyset]$$ не больше $$|G|\left(1-|X|/|G|\right)^k$$ (вероятность объединения событий не больше суммы вероятностей этих событий). Итак, при$$|G|\left(1-\frac{|X|}{|G|}\right)^k<1$$ условие (4.1) заведомо выполняется.

Рассмотрим теперь некоторый язык $$L\in\BPP$$. Для него, как объяснялось выше, можно найти полиномиально вычислимый предикат $$R(x,y)$$ и полином $$p(\cdot)$$ такие, что число $$|X_x|/2^{p(|x|)}$$, где $$X_x= \{y: (|y|\double=p(|x|))\wedge R(x,y)\}$$, различает слова, принадлежащие языку (для них оно больше $$1-\eps$$ ), и слова, языку не принадлежащие (для таких слов это число меньше $$\eps$$ ). Параметр $$\eps$$ мы выберем позже, сейчас отметим, что его величина может быть экспоненциально мала, как объяснялось в лекции 3 после определения 3.1.

Введем искусственно структуру группы на множестве слов $$y$$ длины $$p(|x|)$$ так, чтобы произведение и обращение элемента в этой группе были полиномиально вычислимыми (например, в качестве групповой операции возьмем покомпонентное сложение по модулю два). Запишем следующее $$\Sigma_2$$ -условие$$\exists\, g_1,\dots, g_k\:\forall\, y\: \big((|y|=p(|x|))\Rightarrow\\ \Rightarrow \left((y\in g_1 X_x)\vee(y\in g_2X_x)\vee\dots\vee(y\in g_k X_x)\right)\big).$$ Другими словами, рассматриваем такую игру: белые своим ходом называют $$k$$ слов (элементов группы), а черные — один элемент, который, по их мнению, не покрыт сдвигами множества $$X_x$$ на слова $$g_i$$, названные белыми.

Условие (4.2) в этом случае имеет вид $$\eps k<1 $$, а условие (4.3): $$2^{p(|x|)}\eps^k<1$$. Эти условия выполняются при подходящем выборе параметров. Можно взять $$k$$ порядка $$p(|x|)$$ и $$\eps$$ порядка $$p^{-1}(|x|)$$.

Замечание 4.1. Имеется рассуждение, которое "показывает", что время вычисления функций из класса BPP можно сделать, по-видимому, меньше $$2^{n^\eps}$$ для любого $$\eps$$. Идея состоит в том, чтобы использовать генераторы псевдослучайных чисел. Такой генератор по набору битов длины $$k$$ строит набор длины $$k'$$, где $$k'\gg k$$. Если при этом выбирать короткие наборы случайно, то длинные наборы будут распределены так, что вычислительное устройство с ограниченными ресурсами (например, полиномиальная машина Тьюринга) не сможет отличить их от по-настоящему случайных. Это пояснение заменяет точное определение псевдослучайного генератора, которое нам не понадобится.

Существуют ли псевдослучайные генераторы, неизвестно. Их заведомо нет, если $$\P=\NP$$. Но в этом случае $$\P=\Sigma_2=\BPP$$.

Если же $$\P\ne\NP$$ и есть псевдослучайные генераторы, то можно находить за указанное выше время значение функции $$f\in\BPP$$, вычисляя значения предиката $$R(x,y)$$ из опр. 3.2 только для псевдослучайных $$y$$.

Остается "небольшой" дефект в этом рассуждении: оно не проходит при $$\P\ne\NP$$ и отсутствии псевдослучайных генераторов. Такая ситуация считается маловероятной.

Класс PSPACE.

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

Теорема 4.2. $$L\in\PSPACE$$ тогда и только тогда, когда существует такая игра с полиномиальным от длины входного слова числом ходов и полиномиально вычислимым результатом, что $$L=\{x\:\big|$$ Б имеет выигрышную стратегию $$\}$$.

Доказательство $$\Longleftarrow\quad$$ Покажем, что язык, определяемый игрой, принадлежит $$\PSPACE$$. Пусть число ходов ограничено $$p(|x|)$$. Определим по индукции набор машин Тьюринга $$M_k$$ для $$k=0,\dots,p(|x|)$$. Каждая $$M_k$$ по заданному началу игры $$x,w_1,b_1,\dots$$ длины $$k$$ определяет наличие выигрышной стратегии у Б. Последней в этом ряду машине $$M_{p(|x|)}$$ нужно просто вычислить предикат $$W(x,w_1,\dots)$$. Машина $$M_k$$ перебирает все возможные варианты $$(k+1)$$ -го хода и консультируется с $$M_{k+1}$$ по поводу окончательных результатов игры. Ее оценка игры составляется очень просто: если текущий ход у Б, то достаточно найти один ход, при котором $$M_{k+1}$$ гарантирует выигрышную стратегию для Б. Если текущий ход у Ч, то при всех вариантах $$M_{k+1}$$ должна обнаружить выигрышную стратегию для Б. Машина $$M_0$$ определяет наличие выигрышной стратегии для Б в самом начале игры и для ее работы нам нужно использовать всю последовательность машин $$M_k$$. Но каждая из этих машин использует небольшую (полиномиально ограниченную) память, так что весь процесс потребует лишь полиномиально ограниченной памяти.

$$\Longrightarrow\quad$$ Пусть есть машина $$M$$, распознающая вхождение слова в язык $$L$$ на полиномиальной памяти. Во-первых, заметим, что вычисление на памяти $$S$$ бессмысленно проводить дольше, чем время $$2^{O(S)}$$ (все начнет повторяться после того, как мы исчерпаем все состояния нашей системы, а их не более чем $$|\calA|^S\cdot|\calQ|\cdot S$$, где $$\calQ,\calA$$ — соответственно множество состояний управляющего устройства и алфавит рассматриваемой МТ). Поэтому можно считать без ограничения общности, что время работы машины $$M$$ ограничено $$2^q$$, где $$q=O(p(|x|))$$.

Чтобы было проще описывать игру, потребуем, чтобы после завершения вычисления МТ сохраняла без изменений достигнутое состояние.

Игра заключается в следующем. Белые утверждают, что ответ на входном слове $$x$$ равен "да", а черные хотят это проверить. Белые своим первым ходом декларируют состояние машины $$M$$ (строка, записанная на ленте, положение читающей головки, состояние управляющего устройства) после $$2^{q-1}$$ тактов. Черные своим ходом выбирают один из промежутков: от начала до $$(2^{q-1})$$ -го такта или от $$(2^{q-1})$$ -го такта до конца. Белые декларируют состояние $$M$$ в середине этого промежутка. Далее все повторяется: Ч выбирает одну из половинок, Б декларирует состояние $$M$$ в середине выбранной половинки и т.д.

Игра заканчивается, когда длина промежутка становится равной 1. Результат определяется так: для обоих концов этого промежутка в процессе игры были названы состояния $$M$$. Если состояние правого конца получается из состояния левого конца за один такт работы $$M$$, то Б выиграли, иначе выиграли Ч.

Если ответ $$M$$ на слове $$x$$ действительно "да", то белым нужно все время говорить правду, это гарантирует им выигрыш.

Если ответ $$M$$ на слове $$x$$ — "нет", то при любом ходе белых на одном из промежутков (или на обоих) будет содержаться ошибка. Ч должен указывать каждый раз именно этот промежуток.

Задача 4.1. Докажите, что класс языков, распознаваемых недетерминированными машинами, работающими на памяти $$S$$, содержится в классе языков, распознаваемых детерминированными машинами, работающими на памяти $$\poly(S)$$.

В качестве следствия теоремы 4.2 получаем включения всех определенных выше классов $$\Sigma_k$$, $$\Pi_k$$ в класс $$\PSPACE$$. Взаимное соотношение этих классов можно изобразить диаграммой включений, показанной ниже. На этой диаграмме от большего класса к меньшему можно пройти, двигаясь по стрелкам. Внизу располагается класс $$\P$$, отвечающий играм с 0 ходов, затем идут дополняющие друг друга классы, отвечающие играм с конечным числом ходов (для одного хода это NP и co-NP, для двух ходов — $$\Sigma_2$$ и $$\Pi_2$$ и т.д.). Завершается эта диаграмма классом $$\PSPACE$$, который определяется произвольными играми с одним естественным условием — время игры должно быть полиномиально ограничено размером входного слова. Мы уже доказали все включения, изображенные на этой диаграмме. Ни про одно из включений, следующих из этой диаграммы, неизвестно, является ли оно строгим. Быть может, скажем, $$\P=\PSPACE$$. С другой стороны, возможно и так, что $$\PSPACE=\mathrm{EXPTIME}$$, где $$\mathrm{EXPTIME}$$ обозначает (не рассматривавшийся нами) класс языков, вычислимых за экспоненциальное время $$2^{\poly(n)}$$. Впрочем, наиболее популярна гипотеза о том, что все включения, изображенные на диаграмме — строгие.

(рис 4.1)

Задача 4.2. Машина Тьюринга с оракулом $$A$$ — это МТ с дополнительной оракульной лентой, куда она (машина) может записывать слова, а затем за один такт работы проверять, принадлежит ли записанное на оракульной ленте слово языку $$A$$. По двум сложностным классам $$\calX$$ и $$\calY$$ можно определить класс $$\calX^{\calY}$$ таких языков, которые распознаются машинами из класса $$\calX$$ с оракулами из $$\calY$$.

Докажите, что $$\P^{\Sigma_k}=\P^{\Pi_k}\subseteq \Sigma_{k+1}\cap \Pi_{k+1}$$.

В классе $$PSPACE$$ существуют полные задачи (относительно полиномиальной сводимости). Простейший вариант получается применением предыдущей теоремы.

Задача $$TQBF$$. Задается предикатом

$$TQBF(x)$$ $$\Leftrightarrow$$ $$x$$ есть истинная булева формула с кванторами (True Quantified Boolean Formula), т.е. формула вида$$\mathsf{Q}_1\, y_1\dots\mathsf{Q}_n\, y_n F(y_1,\dots,y_n),$$ где $$y_i\in\cb$$, $$F$$ — некоторая логическая формула, а $$\mathsf{Q}_i$$ — либо $$\forall$$, либо $$\exists$$. По определению, $$\left(\forall\, y_1\: A(y_1)\right)\double=\left(A(0)\wedge A(1)\right)$$, а $$\left(\exists\, y_1\: A(y_1)\right)=\left(A(0)\vee A(1)\right)$$.

Теорема 4.3. $$TQBF PSPACE$$ -полна.

Доказательство. Построим сведение любого языка $$L\in\PSPACE$$ к задаче c TQBF. Для этого превратим МТ, вычисляющую результат игры (предикат $$W(\cdot)$$ ), в схему, а ходы игроков закодируем булевыми переменными. Тогда наличие выигрышной стратегии у белых задается условием$$\exists\, w^1_1\: \exists\, w^2_1\: \dots \exists\, w^{p(|x|)}_1 \:\forall\, b^1_1\: \dots\: \forall\, b^{p(|x|)}_1\: S(x,w^1_1,w^2_1,\dots),$$ где $$S(\cdot)$$ обозначает результат вычисления по схеме.

Чтобы превратить $$S$$ в булеву формулу, добавим новые переменные $$y_i$$ (значение, вычисленное при $$i$$ -м присваивании в схеме) и заменим $$S(\cdot)$$ на формулу вида$$\exists\, y_1,\dots, \exists\, y_{\text{размер схемы}}\: \left(y_1\Leftrightarrow R_1\right)\wedge\dots \wedge\left(y_{s}\Leftrightarrow R_s\right)\wedge y_s,$$ где $$s$$ — размер схемы, $$R_i$$ — правая часть $$i$$ -го присваивания.

После этой подстановки получим квантифицированную булеву формулу, которая истинна в точности для $$x\in L$$.

Страницы: