Теорема о соотношении coNP и IP

Подготовка к доказательству

Определение:

[math]\mathrm{\#SAT}=\{\langle \varphi, k \rangle \mid \varphi[/math] — булева формула, которая имеет ровно [math]k[/math] удовлетворяющих наборов [math]\}[/math].

Лемма (1):

Пусть [math] \varphi [/math] булева формула, а [math] A_\varphi [/math] — её арифметизация. Тогда [math]\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\varphi(x_1, \ldots, x_m)=k \Leftrightarrow \langle \varphi,k\rangle \in \mathrm{\#SAT}[/math].

Доказательство:

[math]\triangleright[/math]

Следует из леммы (1).

[math]\triangleleft[/math]

Лемма (2):

[math]\mathrm{\#SAT} \in \mathrm{IP}[/math].

Доказательство:

[math]\triangleright[/math]

Сперва арифметизуем формулу [math]\varphi[/math]. Пусть полученный полином [math]A_\varphi(x_1, x_2, \ldots, x_m)[/math] имеет степень [math]d[/math]. Для доказательства леммы построим программы [math]V[/math] ([math] \mathrm{Verifier}[/math]) и [math]P[/math] ([math]\mathrm{Prover}[/math]) из определения класса [math]\mathrm{IP}[/math]. По лемме (1) вместо условия [math]\langle \varphi, k \rangle \in \mathrm{\#SAT}[/math], можно проверять условие [math]\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\varphi(x_1, \ldots, x_m)=k[/math]. Тогда пусть на вход протоколу поступает пара [math] \langle A_{\varphi}, k \rangle [/math]. Приступим к описанию интерактивного протокола. Шаг 0 Если [math]d=0[/math] или [math]m=0[/math], то [math]V[/math] может проверить указанное выше условие сам и вернуть соответствующий результат. Иначе запросим у [math]P[/math] такое простое число [math]p[/math], что [math]3dm \leqslant p \leqslant 6dm[/math] (такое [math]p[/math] существует в силу постулата Бертрана. Проверим [math]p[/math] на простоту и на принадлежность заданному промежутку. Как мы знаем, [math]\mathrm{Primes} \in \mathrm{P}[/math], следовательно на эти операции у [math]V[/math] уйдёт полиномиальное от размера входа время. Далее будем проводить все вычисления по модулю [math]p[/math], то есть над конечным полем [math] \mathbb{F}_{p} [/math], что не позволяет числам становиться слишком большими и упрощает анализ. Попросим [math]P[/math] прислать [math]V[/math] формулу [math]A_0(x_1)= \sum\limits_{x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A_\varphi(x_1, x_2, \ldots, x_m)[/math]. Заметим, что размер формулы [math]A_0(x_1)[/math] будет полином от длины входа [math]V[/math], так как [math]A_0(x_1)[/math] — полином степени не выше, чем [math]d[/math], от одной переменной, а значит его можно представить в виде [math]A_0(x) = \sum\limits_{i = 0}^{d} C_i \cdot x ^ i[/math]. Проверим следующее утверждение: [math]A_0(0) + A_0(1) = k[/math] (*) (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, [math]V[/math] продолжает свою работу, иначе он прекращает свою работу и возвращет false). Шаг i Пусть [math]r_i = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace[/math]. Отправим [math]r_i[/math] программе [math]P[/math]. Попросим [math]P[/math] прислать [math]V[/math] формулу [math]A_i(x_{i+1}) = \sum\limits_{x_{i+2} = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A_\varphi(r_1,\ldots, r_i, x_{i+1}, \ldots, x_m)[/math]. Проверим следующее утверждение: [math]A_i(0) + A_i(1) = A_{i-1}(r_i)[/math] (*). Шаг m Пусть [math]r_m = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace[/math]. Отправим [math]r_m[/math] программе [math]P[/math]. Попросим программу [math]P[/math] прислать [math]V[/math] значение [math]A_m()= A_\varphi(r_1, r_2, \ldots, r_m)[/math]. Проверим следующее утверждение: [math]A_m() = A_{m-1}(r_m)[/math] (*). А также сами подставим [math]r_1, r_2, \ldots, r_m[/math] в [math]A_\varphi(x_1, x_2, \ldots, x_m)[/math] и проверим правильность присланного значения [math]A_m()[/math]. Возвращаем true. Докажем теперь, что построенный таким образом интерактивны протокол — корректный. Для этого нужно доказать следующие утверждения: Построенный [math]V[/math] — вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий. [math]\langle \varphi, k \rangle \in \mathrm{\#SAT} \Rightarrow \exists P : \mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \geqslant 2/{3}[/math] (Completeness). [math]\langle \varphi, k \rangle \notin \mathrm{\#SAT} \Rightarrow \forall P :\mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \leqslant 1/{3}[/math] (Soundness). Докажем эти утверждения. Первый факт следует из построения [math]V[/math]. По лемме (2), если [math]\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\varphi(x_1, \ldots, x_m)=k[/math], то условия (*) выполняются, а значит, по построению протокола, существует такой [math]P[/math], что [math]\mathbb{P}(V_{P}(\langle\varphi,k\rangle) = 1) = 1[/math], для любой пары [math]\langle\varphi,k\rangle \in \mathrm{\#SAT}[/math]. Пусть количество наборов, удовлетворяющих [math]\varphi[/math], не равно [math]k[/math]. Для того, чтобы [math]V[/math] вернул true, [math]P[/math] должен посылать такие [math]A_i[/math], чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать: Шаг 0 Так как количество наборов, удовлетворяющих [math]\varphi[/math], не равно [math]k[/math], то [math]P[/math] не может послать правильное [math]A_0[/math], поскольку в этом случае не выполнится условие [math]A_0(0) + A_0(1) = k[/math]. Поэтому он посылает не [math]A_0[/math], а некое [math]\tilde{A}_0[/math]. Шаг i Заметим, что если на каком-то шаге [math]A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)[/math], то начиная со следующего шага [math]P[/math] может посылать правильные [math]A_j[/math] и в итоге [math]V[/math] вернёт true. Для некоторого случайно выбранного [math]r_i[/math] вероятность того, что [math]A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)[/math], не превосходит [math]\dfrac{d}{p}[/math], так как [math]r_i[/math] — корень полинома [math](A_{i-1} - \tilde{A}_{i-1})(r_i)[/math], имеющего степень не больше [math]d[/math], а, по основной теореме алгебры, полином имеет ровно [math] d [/math] корней, и [math] r_i \in \lbrace 0, \ldots, p -1 \rbrace[/math]. Шаг m Так как на последнем шаге [math]V[/math] сверяет полученное от [math]P[/math] значение с непосредственно вычисленным, слово будет допущено только в том случае, когда [math]P[/math] смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома. Вычислим вероятность того, что хотя бы раз корень был угадан. [math]\mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) = 1 - \left( 1 - \dfrac{d}{p} \right)^m \leqslant 1 - \left(1 - \dfrac{d}{3dm}\right)^m = 1 - \left(1 - \dfrac{1}{3m}\right)^m [/math]. Заметим, что функция [math] y(m) = 1 - \left( 1 - \dfrac{1}{3m} \right)^{m}[/math] убывает при [math] m \geqslant \dfrac{1}{3} [/math]. А так как [math] m \geqslant 1 [/math] и [math] y(1) = \dfrac{1}{3} [/math], в итоге получаем, что [math]\mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \leqslant \dfrac{1}{3} [/math]. Таким образом, построенный нами интерактивный протокол корректен, а значит лемма доказана.

[math]\triangleleft[/math]

Теорема

Теорема:

[math]\mathrm{coNP} \subset \mathrm{IP}[/math].

Доказательство:

[math]\triangleright[/math]

Сведём язык [math]\mathrm{TAUT}[/math] к языку [math]\mathrm{\#SAT}[/math] следующим образом: [math]\varphi \mapsto \langle \varphi, 2^k \rangle [/math], где [math]k[/math] — количество различных переменных в формуле [math]\varphi[/math]. [math]\varphi \in \mathrm{TAUT} \Leftrightarrow \forall x = (x_1, \ldots, x_k) \varphi(x) = 1 \Leftrightarrow \exists 2^{k} [/math] удовлетворяющих наборов [math] x [/math] для [math] \varphi(x) \Leftrightarrow \langle \varphi, 2^k \rangle \in \mathrm{\#SAT}[/math]. По лемме (2) [math]\mathrm{\#SAT} \in \mathrm{IP}[/math]. Тогда [math]\mathrm{TAUT} \in \mathrm{IP}[/math]. Так как [math]\mathrm{TAUT} \in \mathrm{coNPC}[/math], то [math]\mathrm{coNP} \subset \mathrm{IP}[/math].

[math]\triangleleft[/math]

См. также

• Интерактивные протоколы. Класс IP. Класс AM
• Арифметизация булевых формул с кванторами
• Вероятностные вычисления. Вероятностная машина Тьюринга
• Теорема Бермана — Форчуна
• Классы NP, coNP, Σ₁, Π₁