Лемма о соотношении coNP и IP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 60: Строка 60:
 
Докажем теперь, что построенный таким образом ''Verifier'' — корректный. Для этого нужно доказать следующие утверждения:
 
Докажем теперь, что построенный таким образом ''Verifier'' — корректный. Для этого нужно доказать следующие утверждения:
 
# Построенный ''Verifier'' - вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
 
# Построенный ''Verifier'' - вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
# <tex>\langle \varphi, k \rangle \in \#SAT \Rightarrow \exists \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)) \ge 2/3</tex>.
+
# <tex>\langle \varphi, k \rangle \in \#SAT \Rightarrow \exists \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \ge 2/3</tex>.
# <tex>\langle \varphi, k \rangle \notin \#SAT \Rightarrow \forall \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)) \le 1/3</tex>.
+
# <tex>\langle \varphi, k \rangle \notin \#SAT \Rightarrow \forall \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \le 1/3</tex>.
  
 
Докажем эти утверждения.
 
Докажем эти утверждения.
Строка 76: Строка 76:
 
:<tex>\ldots</tex>
 
:<tex>\ldots</tex>
 
:'''Шаг m'''
 
:'''Шаг 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'' вернет ''false''.  
+
:Допустим до шага <tex>m</tex> мы ни разу не угадали корень <tex>r_i</tex>, то есть ''Prover'' каждый обманывал ''Verifier''. Так как на последнем шаге сверяем истинное значение с присланным ''Prover'' 'ом, то ''Verifier'' не допустит слово. Значит ''Verifier'' могу допустить слово только если на каком-то шаге был угадан корень.
 
:
 
:
:Из описанного процесса видно, что с вероятностью большей либо равной <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''.
+
:<tex>P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \le \frac d p \sum \limits_{i=0}^{m-1} (1 - \frac d p)^i = 1 - (1 - \frac d p)^m \le 1 - (1 - \frac d {3dm})^m = 1 - (1 - \frac 1 {3m})^m \le \frac 1 3</tex>.
:Оценим вероятность возврата ''Verifier'' 'ом ответа '''false'''.
 
:<tex>P(!\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)) \ge (1 - \frac d p) ^ m \ge (1 - \frac d {3dm})^m = (1 - \frac 1 {3m})^m = 1 - \frac 1 3 + \frac{m(m - 1)}{2 (3m)^2}  - \frac{m(m-1)(m-2)}{6 (3m)^3} + \ldots \ge \frac 2 3</tex>.
 
  
 
Таким образом, построенный нами ''Verifier'' корректен, а значит лемма доказана.
 
Таким образом, построенный нами ''Verifier'' корректен, а значит лемма доказана.

Версия 16:07, 4 июня 2012

Эта статья находится в разработке!


Определение:
[math]\mathrm{\#SAT}=\{\langle \varphi, k \rangle \bigm| \varphi[/math] имеет ровно [math]k[/math] удовлетворяющих наборов [math]\}[/math].


Лемма (1):
[math]\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\phi(x_1, \ldots, x_m)=k \Leftrightarrow \langle\phi,k\rangle \in \mathrm{\#SAT}[/math].
Доказательство:
[math]\triangleright[/math]
Следует из леммы (1).
[math]\triangleleft[/math]


Лемма (2):
[math]\mathrm{\#SAT} \in \mathrm{IP}[/math].
Доказательство:
[math]\triangleright[/math]

Для доказательства леммы построим программы Verifier и Prover из определения класса [math]\mathrm{IP}[/math].

Сперва арифметизуем формулу [math]\phi[/math]. Пусть полученный полином [math]A(x_1, x_2, ..., x_m)[/math] имеет степень [math]d[/math].

По лемме (1) вместо условия [math]\langle \phi, k \rangle \in \mathrm{\#SAT}[/math], можно проверять условие [math]\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\phi(x_1, \ldots, x_m)=k[/math].

Приступим к описанию Verifier'а.

Шаг 0

Если [math]d=0[/math] или [math]m=0[/math], то Verifier может проверить указанное выше условие сам и вернуть соответствующий результат. Иначе запросим у Prover'а такое простое число [math]p[/math], что [math]3dm \le p \le 6dm[/math] (такое [math]p[/math] существует в силу постулата Бертрана). Проверим [math]p[/math] на простоту и на принадлежность заданному промежутку. Как мы знаем, [math]\mathrm{Primes} \in \mathrm{P}[/math], следовательно на эти операции у Verifier'а уйдёт полиномиальное от размера входа время.

Далее будем проводить все вычисления модулю [math]p[/math].

Попросим Prover 'а прислать Verifier 'у формулу [math]A_0(x_1)= \sum\limits_{x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A(x_1, x_2, ..., x_m)[/math]. Заметим, что размер формулы [math]A_0(x_1)[/math] будет полином от длины входа Verifier 'а, так как [math]A_0(x_1)[/math] — полином степени не выше, чем [math]d[/math], от одной переменной, а значит его можно представить в виде [math]A_0(x) = \sum\limits_{i = 0}^{d} C_i \cdot x ^ i[/math].

Проверим следующее утверждение: [math]A_0(0) + A_0(1) = k[/math] (*) (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, Verifier продолжает свою работу, иначе он прекращает свою работу и возвращет false).

Шаг i

Пусть [math]r_i = random(p)[/math]. Отправим [math]r_i[/math] программе Prover.

Попросим Prover 'а прислать Verifier 'у формулу [math]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)[/math].

Проверим следующее утверждение: [math]A_i(0) + A_i(1) = A_{i-1}(r_i)[/math] (*).

Шаг m

Пусть [math]r_m = random(p)[/math]. Отправим [math]r_m[/math] программе Prover.

Попросим программу Prover прислать Verifier 'у значение [math]A_m()= A(r_1, r_2, ..., r_m)[/math].

Проверим следующее утверждение: [math]A_m() = A_{m-1}(r_m)[/math] (*). А также сами подставим [math]r_1, r_2, ..., r_m[/math] в [math]A(x_1, x_2, ..., x_m)[/math] и проверим правильность присланного значения [math]A_m()[/math].

Возвращаем true.

Докажем теперь, что построенный таким образом Verifier — корректный. Для этого нужно доказать следующие утверждения:

  1. Построенный Verifier - вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
  2. [math]\langle \varphi, k \rangle \in \#SAT \Rightarrow \exists \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \ge 2/3[/math].
  3. [math]\langle \varphi, k \rangle \notin \#SAT \Rightarrow \forall \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \le 1/3[/math].

Докажем эти утверждения.

  1. Первый факт следует из построения Verifier 'а.
  2. По лемме (2), если [math]\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\phi(x_1, \ldots, x_m)=k[/math], то условия (*) выполнятются, следовательно существует такой Prover, что [math]P(\mathit{Verifier^{Prover}}(\langle\phi,k\rangle)) = 1[/math], для любой пары [math]\langle\phi,k\rangle \in \mathrm{\#SAT}[/math].
  3. Пусть количество наборов, удовлетворяющих [math]\phi[/math], не равно [math]k[/math]. Для того, что бы Verifier вернул true, Prover 'у необходимо посылать такие [math]A_i[/math], чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
Шаг 0
Так как количество наборов, удовлетворяющих [math]\phi[/math], не равно [math]k[/math], то Prover не может послать правильное [math]A_0[/math], поскольку в этом случае не выполнится условие [math]A_0(0) + A_0(1) = k[/math]. Поэтому он посылает не [math]A_0[/math], а некое [math]\tilde{A}_0[/math].
[math]\ldots[/math]
Шаг i
Заметим, что если на каком-то шаге [math]A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)[/math], то начиная со следующего шага Prover может посылать истинные значения [math]A_j[/math] и в итоге Verifier вернёт true.
Для некоторого случайно выбранного [math]r_i[/math] вероятность того, что [math]A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)[/math], то есть [math]r_i[/math] — корень полинома [math](A_{i-1} - \tilde{A}_{i-1})(r_i)[/math], имеющего степень не больше [math]d[/math], не превосходит [math]\frac{d}{p}[/math].
[math]\ldots[/math]
Шаг m
Допустим до шага [math]m[/math] мы ни разу не угадали корень [math]r_i[/math], то есть Prover каждый обманывал Verifier. Так как на последнем шаге сверяем истинное значение с присланным Prover 'ом, то Verifier не допустит слово. Значит Verifier могу допустить слово только если на каком-то шаге был угадан корень.
[math]P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \le \frac d p \sum \limits_{i=0}^{m-1} (1 - \frac d p)^i = 1 - (1 - \frac d p)^m \le 1 - (1 - \frac d {3dm})^m = 1 - (1 - \frac 1 {3m})^m \le \frac 1 3[/math].
Таким образом, построенный нами Verifier корректен, а значит лемма доказана.
[math]\triangleleft[/math]


Лемма (3):
[math]\mathrm{coNP} \subset \mathrm{IP}[/math].
Доказательство:
[math]\triangleright[/math]

Сведём язык [math]\mathrm{TAUT}[/math] к языку [math]\mathrm{\#SAT}[/math] следующим образом: [math]\phi \mapsto \langle \phi, 2^k \rangle [/math], где [math]k[/math] — количество различных переменных в формуле [math]\phi[/math].

Очевидно, что [math]\phi \in \mathrm{TAUT} \Leftrightarrow \langle \phi, 2^k \rangle \in \mathrm{\#SAT}[/math].

По лемме (2) [math]\mathrm{\#SAT} \in \mathrm{IP}[/math]. Тогда [math]\mathrm{TAUT} \in \mathrm{IP}[/math]. Так как [math]\mathrm{TAUT} \in \mathrm{coNPC}[/math], то [math]\mathrm{coNP} \subset \mathrm{IP}[/math].
[math]\triangleleft[/math]