Научная Сеть >> М.Н. Вялый "Сложность вычислительных задач"

Наука >> Математика >> Математическое образование | Популярные статьи

Next: 9. Заключение Up: 8. Класс IP Previous: 8.3. Contents: Содержание

8.4.

Дадим набросок доказательства, подробно это доказательство изложено в книге Сипсера [9].

Достаточно доказать, что $\ensuremath{\mathrm{PSPACE}}$ -полная задача $\ensuremath{\mathrm{TQBF}}$ принадлежит $\ensuremath{\mathrm {IP}}$ .

Итак, пусть нужно проверить истинность высказывания

$\begin{displaymath} T_0=\ensuremath{\mathsf{Q}}_1x_1\ensuremath{\mathsf{Q}}_2x_2\dots \ensuremath{\mathsf{Q}}_mx_m \varphi(x_1,\dots,x_m), \end{displaymath}$

в котором $\varphi(\cdot)$ - некоторая логическая формула, $\ensuremath{\mathsf{Q}}_i\in \{\forall,\exists\}$ , кванторы действуют на формулы по правилам (14)-(15).

Оценить истинность высказывания можно следующей рекурсивной процедурой. Обозначим через $T_j(x_1,x_2,\dots,x_j)$ высказывание

$\begin{displaymath} \ensuremath{\mathsf{Q}}_{j+1}x_{j+1}\ensuremath{\mathsf{Q}}_... ...h{\mathsf{Q}}_mx_m \varphi(x_1,\dots,x_j, x_{j+1},\dots, x_m). \end{displaymath}$

Тогда $T_0=T_1(0)\ast_1 T_1(1)$ , где $\ast_1$ - связка, определяемая квантором $\ensuremath{\mathsf{Q}}_1$ . Найдем вначале

, а затем

, каждый раз вызывая рекурсивно саму описываемую процедуру (для определения $T_m(x_1,\dots, x_m)$ достаточно вычислить значение формулы $\varphi(x_1,\dots,x_m)$ , так что рекурсия конечная) и вычислим $T_1(0)\ast_1 T_1(1)$ .

Эта процедура требует вычисления всех возможных значений формулы $\varphi(\cdot)$ , а потому занимает экспоненциально большое по сравнению с размером входа задачи время. Наглядно это вычисление можно изобразить в виде дерева, как показано на рис. 4а. В процессе вычисления мы получаем не только значение в корне, но и значения во всех промежуточных узлах дерева, количество которых экспоненциально велико.

Чем может помочь Советник в таком вычислении? Он, конечно, может сообщить значение . Впрочем, поскольку Советник пристрастен, то в любом случае он скажет, что . Попробуем проверить это сообщение и запросим значения и - должно выполняться соотношение $T_0\relax =T_1(0)\ast_1 T_1(1)$ . Далее выберем случайно и равновероятно число $r_1\in\{0,1\}$ , запросим у Советника значения и , проверим $T_1(r_1)=T_2(r_1,0)\ast_2 T_2(r_1,1)$ и т. д. На последнем шаге уже без всякого Советника можно проверить, что

$\begin{displaymath}T_{m-1}(r_1,\dots,r_{m-1})=T_{m}(r_1,\dots,r_{m-1},0)\ast_m T_{m}(r_1,\dots,r_{m-1},1).\end{displaymath}$

Вычисления будут длиться $O(m)+\Phi(n)=\mathop{\mathrm{poly}}\nolimits (n)$ тактов, где $\Phi(n)$ - количество тактов, необходимых для вычисления значения логической формулы длины при заданных значениях переменных. Они происходят вдоль одного из путей от корня к листьям в дереве на рис. 4а, выбираемого случайно и равновероятно.

Рис. 4.

$\begin{figure}\begin{center} \begin{tabular}{@{}cc@{}} \epsfbox{ccnp.3}&\epsfbox{ccnp.4}\\ а)& б) \end{tabular}\end{center}\end{figure}$

С какой вероятностью Исполнитель принимает решение об истинности QBF? Если рассматриваемая формула истинна, то Советнику достаточно говорить истинные значения всех запрашиваемых величин, Исполнитель не увидит никакого противоречия и с вероятностью 1 признает формулу истинной. Что будет, если QBF ложна? Чтобы убедить Исполнителя в обратном, Советнику хотя бы раз придется солгать, сообщив неверное значение одной из пары запрашиваемых переменных. Эта ложь с вероятностью замечена не будет, что показывает непригодность описанной процедуры для надежного определения истинности QBF.

Как ни странно, есть способ исправить описанную выше процедуру. Если в исходном варианте из полного бинарного дерева перебора случайно выбирался один путь, и это ничего не дало, то в исправленной версии дерево станет шире (каждый раз будет выбор из вариантов, где $p=\Omega(n^4)$ - простое число) и глубже (глубина дерева была , а в исправленной версии будет примерно ). Это дерево изображено на рис. 4б.

Чтобы построить такое разветвленное дерево, будем считать истинностные значения и элементами поля $\FF_p$ вычетов по модулю . Любую логическую формулу $\varphi(x_1,x_2,\dots,x_m)$ можно записать как многочлен $p(x_1,x_2,\dots,x_m)$ над полем $\FF_p$ , используя выражения (8). Степень этого многочлена не превосходит длины записи формулы $\varphi(\hskip-1.2pt{}x_1,x_2,\dots,x_m\hskip-0.9pt)$ , которая меньше - размера входа задачи $\ensuremath{\mathrm{TQBF}}$ .

Кванторам сопоставим следующие операции с многочленами:

$\begin{displaymath} \forall\ \mapsto A_x f(x_1,\dots,x)\bydef f(x_1,\dots,0)f(x_1,\dots,1), \end{displaymath}$ (17)

$\begin{displaymath} \exists\ \mapsto E_x f(x_1,\dots,x)\bydef 1-(1-f(x_1,\dots,0))(1-f(x_1,\dots,1)). \end{displaymath}$

(18)

Теперь число

$\begin{displaymath} p_0=(Q_1)_{x_1} (Q_2)_{x_2} \dots (Q_m)_{x_m} p(x_1,\dots,x_m) \end{displaymath}$

(19)

равняется истинностному значению формулы $\varphi(x_1,x_2,\dots,x_m)$ (

- операция, соответствующая квантору $\ensuremath{\mathsf{Q}}_i$ ). Вычисление этого числа организовано в дерево, аналогичное изображенным на рис. 4. Степень ветвления у этого дерева равна

, а глубина -

Высказываниям $T_j(x_1,x_2,\dots,x_j)$ при этом соответствуют многочлены

$\begin{displaymath} p_j(x_1,\dots,x_j)=(Q_{j+1})_{x_{j+1}} (Q_{j+2})_{x_{j+2}}\dots (Q_m)_{x_m} p(x_1,\dots,x_j, x_{j+1},\dots, x_m). \end{displaymath}$

Заметим, что операции

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

могут быть велики. Чтобы степени многочленов не росли чрезмерно при вычислениях, можно воспользоваться следующей операцией:

$\begin{displaymath} L_x f(x_1,\dots,x)\bydef xf(x_1,\dots,1)+(1-x)f(x_1,\dots,0). \end{displaymath}$

(20)

Многочлены

имеют одинаковое количество переменных, совпадают при $x\in\{0,1\}$ , а степень переменной

равна 1.

Итак, истинностное значение высказывания равно

$\begin{displaymath} p_0=(Q_1)_{x_1} L_{x_1}(Q_2)_{x_2} L_{x_1} L_{x_2}\dots (Q_m)_{x_m} L_{x_1} L_{x_2}\dots L_{x_m}p(x_1,\dots,x_m), \end{displaymath}$

где

определяется по входу задачи $\ensuremath{\mathrm{TQBF}}$ (так же, как в (19)). К многочлену $p(\cdot)$ применяются в заданном порядке

операций вида

или

. Пусть после применения первых

операций получается многочлен $p_i(t_1,\dots, t_j)$ , $1\leq i\leq k$ . Поскольку операция

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

не обязательно равно

Теперь опишем диалог между Исполнителем и Советником. Начинается он с того, что Советник сообщает значение (как и раньше, в самом начале он скажет, что независимо от его настоящего значения). Затем Исполнитель спрашивает у Советника, чему равен многочлен . Получив коэффициенты этого многочлена, Исполнитель проверяет, что (будем операцию, стоящую на -м месте обозначать ). После этого Исполнитель случайно и равновероятно выбирает число $r_1\in\FF_p$ и применяет рекурсивно ту же процедуру для проверки равенства

$\begin{displaymath} p_1(r_1)= L_{x_1}(Q_2)_{x_2} L_{x_1} L_{x_2}\dots (Q_m)_{x_m} L_{x_1} L_{x_2}\dots L_{x_m}p(x_1,\dots,x_m). \end{displaymath}$

Конечность рекурсии обеспечивается тем, что значение многочлена $p(x_1,\dots,x_m)$ Исполнитель вычисляет самостоятельно. Если все проверки дают положительный результат, Исполнитель выдает в качестве ответа 1, если хотя бы раз обнаружено неравенство - 0.

Теперь оценим вероятности ответа 1.

Если рассматриваемая QBF истинна, то Советнику опять достаточно говорить истинные значения всех запрашиваемых величин. А вот если QBF ложна, Советнику хотя бы раз придется солгать. Поскольку два многочлена степени совпадают не более чем в точках, то с вероятностью не меньшей на следующем шаге будет проверяться ложное условие. По индукции получаем, что вероятность обнаружить ложь в описанном диалоге не меньше

$\begin{displaymath}\left(1- \frac{d}{p}\right)^N, \end{displaymath}$

где

- общее количество проверок. При $p=\Omega(n^4)$ эта вероятность будет близка к 1.

Next: 9. Заключение Up: 8. Класс IP Previous: 8.3. Contents: Содержание

МЦНМО

Написать комментарий