1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''Шаг i'''
Пусть <tex>r_i = random(0..p-1)</tex>. Отправим <tex>r_i</tex> программе ''Prover''.
Попросим ''Prover'' 'а прислать ''Verifier'' 'у формулу <tex>A_i(x_{i+1}) = \sum\limits_{x_{i+2} = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A(r_1,\ldots, r_i, x_{i+1}, ..., x_m)</tex>.
'''Шаг m'''
Пусть <tex>r_m = random(0..p-1)</tex>. Отправим <tex>r_m</tex> программе ''Prover''.
Попросим программу ''Prover'' прислать ''Verifier'' 'у значение <tex>A_m()= A(r_1, r_2, ..., r_m)</tex>.
Докажем теперь, что построенный таким образом ''Verifier'' — корректный. Для этого нужно доказать следующие утверждения:
# Построенный ''Verifier'' - вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
# <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT } \Rightarrow \exists \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \ge 2/3</tex>.# <tex>\langle \varphi, k \rangle \notin \mathrm{\#SAT } \Rightarrow \forall \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \le 1/3</tex>.
Докажем эти утверждения.
:<tex>\ldots</tex>
:'''Шаг i'''
:Заметим, что если на каком-то шаге <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то начиная со следующего шага ''Prover'' может посылать истинные значения правильные <tex>A_j</tex> и в итоге ''Verifier'' вернёт '''true'''.
:Для некоторого случайно выбранного <tex>r_i</tex> вероятность того, что <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то есть <tex>r_i</tex> — корень полинома <tex>(A_{i-1} - \tilde{A}_{i-1})(r_i)</tex>, имеющего степень не больше <tex>d</tex>, не превосходит <tex>\frac{d}{p}</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'' вернет ''falseProver''смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
:
:Из описанного процесса видноВычислим вероятность того, что с вероятностью большей либо равной <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)=1) \ge = 1 - (1 - \frac d p) ^ m \ge le 1 - (1 - \frac d {3dm})^m = (1 - \frac 1 {3m})^m = 1 - le \frac 1 3 + \frac{</tex>.:В последнем переходе мы воспользовались [http://ru.wikipedia.org/wiki/Ряд_Тейлора формулой Тейлора] для логарифма и экспоненты, а также тем, что <tex>m(m - 1)}{2 (3m)^2} - \frac{m(m-1)(m-2)}{6 (3m)^3} + \ldots \ge \frac 2 3>0</tex>.
Таким образом, построенный нами ''Verifier'' корректен, а значит лемма доказана.
