Изменения

Перейти к: навигация, поиск

Лемма о соотношении coNP и IP

97 байт убрано, 15:39, 4 июня 2012
Нет описания правки
Если <tex>d=0</tex> или <tex>m=0</tex>, то ''Verifier'' может проверить указанное выше условие сам и вернуть соответствующий результат.
Иначе запросим у ''Prover'''а такое простое число <tex>p</tex>, что <tex>3dm \le p \le 6dm</tex> (такое <tex>p</tex> существует в силу [http://ru.wikipedia.org/wiki/Постулат_Бертрана постулата Бертрана]).
Проверим <tex>p</tex> на простоту и на принадлежность заданному промежутку. Как мы [[Класс P#Примеры задач и языков из P|знаем]], <tex>\mathrm{Primes } \in \mathrm{P}</tex>, следовательно на эти операции у ''Verifier'''а уйдёт полиномиальное от размера входа время.
Далее будем проводить все вычисления модулю <tex>p</tex>.
Попросим ''Prover'' 'а прислать ''Verifier'' 'у формулу <tex>A_0(x_1)= \sum\limits_{x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A(x_1, x_2, ..., x_m)</tex>.
Заметим, что размер формулы <tex>A_0(x_1)</tex> будет полином от длины входа ''Verifier'' 'а, так как <tex>A_0(x_1)</tex> полином от одной переменной степени не выше, чем <tex>d</tex>, от одной переменной, а значит его можно представить в виде <tex>A_0(x) = \sum\limits_{i = 0}^{d} C_i \cdot x ^ i</tex>.
Проверим следующее утверждение: <tex>A_0(0) + A_0(1) = k</tex> (*) (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, ''Verifier'' продолжает свою работу, иначе он прекращает свою работу и возвращет '''false''').
Докажем теперь, что построенный таким образом ''Verifier'' — корректный. Для этого нужно доказать следующие утверждения:
# Построенный ''Verifier'' - вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
# <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT} \Rightarrow \exists \mathit{Prover } : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)) \ge 2/3</tex>.# <tex>\langle \varphi, k \rangle \notin \mathrm{\#SAT} \Rightarrow \forall \mathit{Prover } : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)) \le 1/3</tex>.
Докажем эти утверждения.
#Первый факт следует из построения ''Verifier'' 'а.
#По [[Арифметизация булевых формул с кванторами | лемме (2)]], если <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\phi(x_1, \ldots, x_m)=k</tex>, то условия (*) выполнятются, следовательно существует такой ''Prover'', что <tex>P(\mathit{Verifier^{Prover}}(\langle\phi,k\rangle)) = 1</tex>, для любой пары <tex>\langle\phi,k\rangle \in \mathrm{\#SAT}</tex>.
#Пусть количество наборов, удовлетворяющих <tex>\phi</tex>, не равно <tex>k</tex>. Для того, что бы ''Verifier'' вернул '''true''', ''Prover'' 'у необходимо посылать такие <tex>A_i</tex>, чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
:'''Шаг 0'''
:Так как количество наборов, удовлетворяющих <tex>\phi</tex>, не равно <tex>k</tex>, то ''Prover'' не может послать правильное <tex>A_0</tex> , поскольку в этом случае не выполнится условие <tex>A_0(0) + A_0(1) = k</tex>. Поэтому он посылает не <tex>A_0</tex>, а некое <tex>\tilde{A}_0</tex>.:<tex>\ldots</tex>:'''Шаг 1i''':По [[Лемма ШварцаЗаметим, что если на каком-Зиппеля|лемме Шварца-Зиппеля]] то шаге <tex>PA_{i-1}(A_0(r_1r_i) = \tilde{A}_0_{i-1}(r_1r_i)) \le \frac d p</tex> для , то начиная со следующего шага ''Prover'' может посылать истинные значения <tex>A_j</tex> и в итоге ''Verifier'' вернёт '''true'''.:Для некоторого случайно выбранного <tex>r_1r_i</tex>. Тогда вероятность того, что <tex>PA_{i-1}(A_0(r_1r_i) \ne = \tilde{A}_0_{i-1}(r_1r_i)) \ge 1 - \frac d p</tex>, при этом должно выполняться равенство то есть <tex>r_i</tex> — корень полинома <tex>A_1(0) + A_1(A_{i-1} - \tilde{A}_{i-1}) = A_0(r_1r_i)</tex>. Значит с вероятностью , имеющего степень не меньше, чем больше <tex>1 - \frac d p</tex>, ''Prover'' отправит ''Verifier'' 'у не превосходит <tex>\tildefrac{d}{Ap}_1</tex> вместо <tex>A_1</tex>.
:<tex>\ldots</tex>
:'''Шаг m'''
: <tex>P(A_{m-1}(r_m) \ne \tilde{A}_{m-1}(r_m)) \ge 1 - \frac d p</tex>. Значит с такой вероятностью ''Verifier'' получит <tex>\tilde{A}_m</tex> вместо <tex>A_m</tex>. Но так как на шаге <tex>m</tex> ''Verifier'' вычисляет <tex>A_m</tex> и сравнивает его с полученным от ''Prover'' 'а, то в этом случае ''Verifier'' вернет ''false''.
:
:Заметим, что если на каком-то шаге <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то начиная со следующего шага ''Prover'' может посылать истинные значения <tex>A_i</tex> и в итоге ''Verifier'' вернёт '''true'''.
:Из описанного процесса видно, что с вероятностью большей либо равной <tex>(1 - \frac d p) ^ m</tex> мы дойдем до последнего шага и будем имееть <tex>\tilde{A}_n</tex> вместо <tex>A_n</tex>. Так как на шаге <tex>m</tex> ''Verifier'' вычисляет <tex>A_n</tex> и проверяет значение, то ''Verifier'' вернет ''false''.
:Оценим вероятность возврата ''Verifier'' 'ом ответа '''false'''.
:<tex>P(!\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)) \ge (1 - \frac d p) ^ m \ge (1 - \frac d {3dm})^m = (1 - \frac 1 {3m})^m = 1 - \frac 1 3 + \frac{m(m - 1)}{2 (3m)^2} - \frac{m(m-1)(m-2)}{6 (3m)^3} + \ldots \ge \frac 2 3</tex>.
Таким образом, построенный нами ''Verifier'' корректен, а значит лемма доказана.

Навигация