Изменения

<tex>\mathrm{\#SAT}=\{\langle \varphi, k \rangle \mid \varphi</tex> {{---}} [[Определение_булевой_функции | булева формула]], которая имеет ровно <tex>k</tex> удовлетворяющих наборов <tex>\}</tex>.

|statement=Пусть <tex> \varphi </tex> булева формула, а <tex> A_\varphi </tex> {{---}} её [[Арифметизация булевых формул с кванторами|арифметизация]]. Тогда <tex>\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}</tex>.

Приступим к описанию интерактивного протоколаСперва арифметизуем формулу <tex>\varphi</tex>. Пусть полученный полином <tex>A_\varphi(x_1, x_2, \ldots, x_m)</tex> имеет степень <tex>d</tex>.

Если По лемме (1) вместо условия <tex>d=0\langle \varphi, k \rangle \in \mathrm{\#SAT}</tex> или , можно проверять условие <tex>m\sum\limits_{x_1 =0</tex>, то <tex>V</tex> может проверить указанное выше условие сам и вернуть соответствующий результат.Иначе запросим у <tex>P</tex> такое простое число <tex>p</tex>, что <tex>3dm }^1 \ldots \sum\leqslant p limits_{x_m = 0}^1 A_\leqslant 6dm</tex> varphi(такое <tex>px_1, \ldots, x_m)=k</tex> существует в силу [http://ru.wikipedia.org/wiki/Постулат_Бертрана постулата Бертрана]). Проверим <tex>p</tex> Тогда пусть на простоту и на принадлежность заданному промежутку. Как мы [[Класс P#Примеры задач и языков из P|знаем]], вход протоколу поступает пара <tex>\mathrmlangle A_{Primes} \in \mathrm{Pvarphi}</tex>, следовательно на эти операции у <tex>Vk \rangle </tex> уйдёт полиномиальное от размера входа время.

Далее будем проводить все вычисления модулю <tex>p</tex>, то есть над конечным полем <tex> \mathbb{F}_{p} </tex>, что не позволяет числам становиться слишком большими и упрощает анализПриступим к описанию [[Интерактивные протоколы. Класс IP. Класс AM|интерактивного протокола]].

Попросим ; '''Шаг 0''':Если <tex>Pd=0</tex> прислать или <tex>Vm=0</tex> формулу , то <tex>A_0(x_1)= \sum\limits_{x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A(x_1, x_2, \ldots, x_m)V</tex>может проверить указанное выше условие сам и вернуть соответствующий результат. Заметим, что размер формулы Иначе запросим у <tex>A_0(x_1)P</tex> будет полином от длины входа такое простое число <tex>Vp</tex>, так как что <tex>3dm \leqslant p \leqslant 6dm</tex>A_0(x_1)такое <tex>p</tex> — полином степени не выше, чем существует в силу постулата Бертрана<ref>[http://ru.wikipedia.org/wiki/Постулат_Бертрана Wikipedia {{---}} Постулат Бертрана]</ref>. Проверим <tex>dp</tex>на простоту и на принадлежность заданному промежутку. Как мы [[Класс P#Примеры задач и языков из P|знаем]], от одной переменной, а значит его можно представить в виде <tex>A_0(x) = \sum\limits_mathrm{i = 0Primes}^\in \mathrm{dP} C_i \cdot x ^ i</tex>, следовательно на эти операции у <tex>V</tex> уйдёт полиномиальное от размера входа время.

Проверим следующее утверждение: Далее будем проводить все вычисления по модулю <tex>A_0(0) + A_0(1) = kp</tex> (*) (здесь , то есть над конечным [[Определение поля и далее под словом «проверим» будем подразумевать следующее: если утверждение верноподполя, изоморфизмы полей | полем ]] <tex>V\mathbb{F}_{p} </tex> продолжает свою работу, иначе он прекращает свою работу что не позволяет числам становиться слишком большими и возвращет '''false''')упрощает анализ.

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

Попросим ; '''Шаг i''':Пусть <tex>Pr_i = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace</tex> прислать . Отправим <tex>Vr_i</tex> формулу программе <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}, \ldots, x_m)P</tex>.

Проверим следующее утверждение: Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>A_i(0) x_{i+ A_i(1}) = A_\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_m = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace</tex>. Отправим <tex>r_m</tex> программе <tex>P</tex>.

Пусть :Попросим программу <tex>r_m = \mathrm{random} \lbrace0, \ldots, p-1 \rbraceP</tex>. Отправим прислать <tex>r_mV</tex> программе значение <tex>PA_m()= A_\varphi(r_1, r_2, \ldots, r_m)</tex>.

Попросим программу :Проверим следующее утверждение: <tex>PA_m() = A_{m-1}(r_m)</tex> прислать (*). А также сами подставим <tex>Vr_1, r_2, \ldots, r_m</tex> значение в <tex>A_mA_\varphi()= A(r_1x_1, r_2x_2, \ldots, r_mx_m)</tex> и проверим правильность присланного значения <tex>A_m()</tex>.

Проверим следующее утверждение: <tex>A_m() = A_{m-1}(r_m)</tex> (*).А также сами подставим <tex>r_1, r_2, \ldots, r_m</tex> в <tex>A(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>\mathit{Prover}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>\mathrm{TAUT}</tex> ]] к языку <tex>\mathrm{\#SAT}</tex> следующим образом: <tex>\varphi \mapsto \langle \varphi, 2^k \rangle </tex>, где <tex>k</tex> — количество различных переменных в формуле <tex>\varphi</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>.