1632
правки
Изменения
м
rollbackEdits.php mass rollback
Итак, надо проверить следующее уравнение: <tex>\sum_{x_1 = 0}^{1}\sum_{x_2 = 0}^{1}...\sum_{x_n = 0}^{1} A(x_1, x_2, ..., x_n) = k</tex>.
Попросим ''Prover'' 'а прислать ''Verifier'' 'у такое простое число <tex>p </tex>, что <tex> max(2^n+1, k_p) \le p \le 2 \cdot max(2^n+1, k_p)</tex> , и сертификат о его простоте. Проверим простоту <tex>p</tex> по сертификату и условие <tex>max(2^n+1, k_p) \le p > \le 2 \cdot max(2^n+1, k_p)</tex>. Константу <tex>k_p</tex> определим позднее.
Далее будем вычислять значения и проверять равенства по модулю <tex>p</tex>.
Проверим следующее утверждение: <tex>A_0(0) + A_0(1) = k</tex>.
Заметим, что размер формулы <tex>A_0(x_1)</tex> будет полином от длинны длины входа ''Verifier'' 'а. Этот факт следует из того, что формула имеет степень меньшую либо равную <tex>d</tex>, и она от одной переменной. Поэтому её можно представить так: <tex>A_0(x) = \sum_{i = 0}^{d} C_i \cdot x ^ i</tex>, и попросить ''Prover'' 'а прислать только сами коэффициенты <tex>C_i</tex> по модулю <tex>p</tex>.
Шаг 1.
Итак, остается доказать, что написанный ''Verifier'' - корректный ''Verifier'' для языка <tex>\#SAT</tex>. Таким образом, нужно доказать:
# Построенный ''Verifier'' - вероятностная машина Тьюринга, совершающая не более полинома от длинны длины входа действий.# <tex><\langle \varphi, k> \rangle \in \#SAT \Rightarrow \exists Prover : P(Verifier^{Prover}(x)) \ge 2/3</tex>.# <tex><\langle \varphi, k> \rangle \notin \#SAT \Rightarrow \forall Prover : P(Verifier^{Prover}(x)) \le 1/3</tex>.
Доказательство:
# Из программы ''Verifier'' видно, что она работает за <tex>O(poly(|input|))</tex>.
# Если <tex>\varphi</tex> имеет ровно <tex>k</tex> удовлетворяющих наборов, то существует такая программа ''Prover'', что <tex>P(Verifier^{Prover}(x)) = 1</tex>. Такая программа:
## Присылает, например, первое простое число, большее <tex>max(2^n+1, k_p)</tex>, и сертификат.
## Считает сумму <tex>A_0(x_1)</tex> и присылает формулу.
## Получает <tex>r_1</tex>.
Из этого процесса заметим, что с вероятностью большей либо равной <tex>(1 - d / p) ^ n</tex> мы дойдем до последнего шага и будем имееть <tex>\tilde{A}_n</tex> вместо <tex>A_n</tex>. Так как на шаге <tex>n</tex> ''Verifier'' вычисляет <tex>A_n</tex> и проверяет значение, то ''Verifier'' вернет ''false''.
Так как мы хотим сделать вероятность возврата ''false'' большую либо равную <tex>2/3</tex>, то выберем <tex>k_p</tex> так, чтобы <tex>(1-d/k_p)^n \ge 2/3</tex>. Возьмем <tex>k_p = 3 d \cdot n</tex>. Заметим, что длина <tex>k_p</tex> есть <tex>poly(|input|)</tex>. Из разложения функции по Тейлору получаем: <tex>(1-d/k_p)^n = (1 - 1/(3n))^n = 1 - 1/3 + \frac{n(n - 1)}{2 (3n)^2} - \frac{n(n-1)(n-2)}{6 (3n)^3} + ... \ge</tex>. Так как <tex>n</tex> - целое неотрицательное число, то: <tex>(1-d/k_p)^n \ge 2/3 + \frac{n(n-1)}{n^2}(\frac{1}{2 \cdot 3^2} - \frac{1}{6 \cdot 3^3}) + ... \ge 2/3</tex>.
Утверждение доказано.
