Изменения

Для доказательства леммы построим программы <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> существует в силу постулата Бертрана<ref>[http://ru.wikipedia.org/wiki/Постулат_Бертрана Wikipedia {{---}} Постулат Бертрана]</ref>. Проверим <tex>p</tex> на простоту и на принадлежность заданному промежутку. Как мы [[Класс P#Примеры задач и языков из P|знаем]], <tex>\mathrm{Primes} \in \mathrm{P}</tex>, следовательно на эти операции у <tex>V</tex> уйдёт полиномиальное от размера входа время.

Если :Далее будем проводить все вычисления по модулю <tex>d=0</tex> или <tex>m=0p</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>\mathrmmathbb{PrimesF} \in \mathrm_{Pp}</tex>, следовательно на эти операции у <tex>V</tex> уйдёт полиномиальное от размера входа времячто не позволяет числам становиться слишком большими и упрощает анализ.

Далее будем проводить все вычисления модулю :Попросим <tex>pP</tex>, то есть над конечным полем прислать <tex>V</tex> формулу <tex> A_0(x_1)= \mathbbsum\limits_{Fx_2 = 0}_^{p1} \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>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_11)= k</tex> будет полином от длины входа <tex>V</tex>, так как <tex>A_0(x_1*)</tex> — полином степени не выше(здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, чем <tex>dV</tex>продолжает свою работу, от одной переменной, а значит его можно представить в виде <tex>A_0(xиначе он прекращает свою работу и возвращет '''false''') = \sum\limits_{i = 0}^{d} C_i \cdot x ^ i</tex>.

Проверим следующее утверждение; '''Шаг i''': Пусть <tex>A_0(0) + A_0(r_i = \mathrm{random} \lbrace0, \ldots, p-1) = k\rbrace</tex>. Отправим <tex>r_i</tex> (*) (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, программе <tex>VP</tex> продолжает свою работу, иначе он прекращает свою работу и возвращет '''false''').

'''Шаг :Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>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)</tex>.

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

:Попросим программу <tex>P</tex> прислать <tex>V</tex> формулу значение <tex>A_iA_m(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}r_2, \ldots, x_mr_m)</tex>.

:Проверим следующее утверждение: <tex>A_i(0) + A_iA_m(1) = A_{im-1}(r_ir_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>.

'''Шаг m''' Пусть <tex>r_m = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace</tex>. Отправим <tex>r_m</tex> программе <tex>P</tex>. Попросим программу <tex>P</tex> прислать <tex>V</tex> значение <tex>A_m()= A_\varphi(r_1, r_2, \ldots, r_m)</tex>. Проверим следующее утверждение: <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>. Возвращаем '''true'''. Докажем теперь, что построенный таким образом интерактивны протокол — {{---}} корректный. Для этого нужно доказать следующие утверждения:# Построенный <tex>V</tex> {{-- -}} [[Вероятностные_вычисления._Вероятностная_машина_Тьюринга|вероятностная машина Тьюринга]], совершающая не более полинома от длины входа действий.# <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT} \Rightarrow \exists P : \mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \geqslant 2/{3}</tex> ([[Интерактивные_протоколы._Класс_IP._Класс_AM|Completeness]]).# <tex>\langle \varphi, k \rangle \notin \mathrm{\#SAT} \Rightarrow \forall P :\mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \leqslant 1/{3}</tex> ([[Интерактивные_протоколы._Класс_IP._Класс_AM|Soundness]]).

::;'''Шаг 0''':::Так как количество наборов, удовлетворяющих <tex>\varphi</tex>, не равно <tex>k</tex>, то <tex>P</tex> не может послать правильное <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>:;'''Шаг i''':::Заметим, что если на каком-то шаге <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то начиная со следующего шага <tex>P</tex> может посылать правильные <tex>A_j</tex> и в итоге <tex>V</tex> вернёт '''true'''.:::Для некоторого случайно выбранного <tex>r_i</tex> вероятность того, что <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, не превосходит <tex>\dfrac{d}{p}</tex>, так как <tex>r_i</tex> — корень полинома <tex>(A_{i-1} - \tilde{A}_{i-1})(r_i)</tex>, имеющего степень не больше <tex>d</tex>, а, по основной теореме алгебры<ref>[https://ru.wikipedia.org/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D1%8B основной теореме Wikipedia {{---}} Основная теорема алгебры]</ref>, полином имеет ровно <tex> d </tex> корней, и <tex> r_i \in \lbrace 0, \ldots, p -1 \rbrace</tex>.:<tex>\ldots</tex>:;'''Шаг m''':::Так как на последнем шаге <tex>V</tex> сверяет полученное от <tex>P</tex> значение с непосредственно вычисленным, слово будет допущено только в том случае, когда <tex>P</tex> смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома. :::Вычислим вероятность того, что хотя бы раз корень был угадан.:::<tex>\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 </tex>.:::Заметим, что функция <tex> y(m) = 1 - \left( 1 - \dfrac{1}{3m} \right)^{m}</tex> убывает при <tex> m \geqslant \dfrac{1}{3} </tex>. А так как <tex> m \geqslant 1 </tex> и <tex> y(1) = \dfrac{1}{3} </tex>, в итоге получаем, что <tex>\mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \leqslant \dfrac{1}{3} </tex>.

Очевидно, что <tex>\varphi \in \mathrm{TAUT} \Leftrightarrow \forall x = (x_1, \ldots, x_k) \varphi(x) = 1 \Leftrightarrow \exists 2^{k} </tex> удовлетворяющих наборов <tex> x </tex> для <tex> \varphi(x) \Leftrightarrow \langle \varphi, 2^k \rangle \in \mathrm{\#SAT}</tex>.