Изменения

Для доказательства леммы построим программы <tex>V</tex> (<tex> \mathrm{Verifier}</tex>) и <tex>P</tex> (<tex>\mathrm{Prover}</tex>) из [[Интерактивные протоколы. Класс IP. Класс AM#Класс IP|определения]] класса <tex>\mathrm{IP}</tex>. По лемме (1) вместо условия <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT}</tex>, можно проверять условие <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\varphi(x_1, \ldots, x_m)=k</tex>. Тогда пусть на вход протоколу поступает пара <tex> \langle A_{\varphi}, k \rangle </tex>.

; '''Шаг 0'''  :Если <tex>d=0</tex> или <tex>m=0</tex>, то <tex>V</tex> может проверить указанное выше условие сам и вернуть соответствующий результат.Иначе запросим у <tex>P</tex> такое простое число <tex>p</tex>, что <tex>3dm \leqslant p \leqslant 6dm</tex> (такое <tex>p</tex> существует в силу [http://ru.wikipedia.org/wiki/Постулат_Бертрана постулата Бертрана]). Проверим <tex>p</tex> на простоту и на принадлежность заданному промежутку. Как мы [[Класс P#Примеры задач и языков из P|знаем]], <tex>\mathrm{Primes} \in \mathrm{P}</tex>, следовательно на эти операции у <tex>V</tex> уйдёт полиномиальное от размера входа время. Далее будем проводить все вычисления по модулю <tex>p</tex>, то есть над конечным полем <tex> \mathbb{F}_{p} </tex>, что не позволяет числам становиться слишком большими и упрощает анализ. Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>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)</tex>. Заметим, что размер формулы <tex>A_0(x_1)</tex> будет полином от длины входа <tex>V</tex>, так как <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> (*) (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, <tex>V</tex> продолжает свою работу, иначе он прекращает свою работу и возвращет '''false'''). '''Шаг i'''

Пусть :Далее будем проводить все вычисления по модулю <tex>r_i = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace</tex>. Отправим , то есть над конечным полем <tex>r_i</tex> программе <tex>P\mathbb{F}_{p} </tex>, что не позволяет числам становиться слишком большими и упрощает анализ.

:Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>A_iA_0(x_{i+1}x_1) = \sum\limits_{x_{i+2} x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A_\varphi(r_1x_1, x_2,\ldots, r_ix_m)</tex>. Заметим, что размер формулы <tex>A_0(x_1)</tex> будет полином от длины входа <tex>V</tex>, так как <tex>A_0(x_1)</tex> — полином степени не выше, чем <tex>d</tex>, x_от одной переменной, а значит его можно представить в виде <tex>A_0(x) = \sum\limits_{i+1= 0}^{d}, C_i \ldots, x_m)cdot x ^ i</tex>.

:Проверим следующее утверждение: <tex>A_iA_0(0) + A_iA_0(1) = A_{i-1}k</tex> (r_i*)(здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, <tex>V</tex> (*продолжает свою работу, иначе он прекращает свою работу и возвращет '''false''').

; '''Шаг mi''':Пусть <tex>r_i = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace</tex>. Отправим <tex>r_i</tex> программе <tex>P</tex>.

Пусть :Попросим <tex>r_m = \mathrm{random} \lbrace0, \ldots, p-1 \rbraceP</tex>. Отправим прислать <tex>r_mV</tex> программе формулу <tex>PA_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)</tex>.

Попросим программу :Проверим следующее утверждение: <tex>PA_i(0) + A_i(1) = A_{i-1}(r_i)</tex> прислать (*).; '''Шаг m''':Пусть <tex>Vr_m = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace</tex> значение . Отправим <tex>A_m()= A_\varphi(r_1, r_2, \ldots, r_m)</tex> программе <tex>P</tex>.

Проверим следующее утверждение: Попросим программу <tex>A_m() = A_{m-1}(r_m)P</tex> (*).А также сами подставим прислать <tex>r_1, r_2, \ldots, r_mV</tex> в значение <tex>A_m()= A_\varphi(x_1r_1, x_2r_2, \ldots, x_m)</tex> и проверим правильность присланного значения <tex>A_m(r_m)</tex>.

Возвращаем '''true''':Проверим следующее утверждение: <tex>A_m() = A_{m-1}(r_m)</tex> (*). А также сами подставим <tex>r_1, r_2, \ldots, r_m</tex> в <tex>A_\varphi(x_1, x_2, \ldots, x_m)</tex> и проверим правильность присланного значения <tex>A_m()</tex>.