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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 26: Строка 26:
 
'''Шаг 0'''  
 
'''Шаг 0'''  
  
Запросим у ''Prover'''а такое простое число <tex>p</tex>, что <tex>max(2^m+1, k_p) \le p \le 2 \cdot max(2^m+1, k_p)</tex>.  
+
Запросим у ''Prover'''а такое простое число <tex>p</tex>, что <tex>max(2^m+1, 3dm) \le p \le 2 \cdot max(2^m+1, 3dm)</tex>.  
Проверим простоту <tex>p</tex> и условие <tex>max(2^m+1, k_p) \le p \le 2 \cdot max(2^m+1, k_p)</tex> (константу <tex>k_p</tex> определим позднее). Как мы [[Класс P#Примеры задач и языков из P|знаем]], <tex>Primes \in \mathrm{P}</tex>, следовательно на эти операции у ''Verifier'''а уйдёт полиномиальное от размера входа время.
+
Проверим <tex>p</tex> на простоту и на принадлежность заданному промежутку. Как мы [[Класс P#Примеры задач и языков из P|знаем]], <tex>Primes \in \mathrm{P}</tex>, следовательно на эти операции у ''Verifier'''а уйдёт полиномиальное от размера входа время.
  
 
Далее будем проводить все вычисления модулю <tex>p</tex>.
 
Далее будем проводить все вычисления модулю <tex>p</tex>.
Строка 40: Строка 40:
 
Пусть <tex>r_i = random(p)</tex>. Отправим <tex>r_i</tex> программе ''Prover''.
 
Пусть <tex>r_i = random(p)</tex>. Отправим <tex>r_i</tex> программе ''Prover''.
  
Пусть <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}, ..., x_m)</tex>.
+
Попросим ''Prover'' 'а прислать ''Verifier'' 'у формулу <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}, ..., x_m)</tex>.
  
Попросим ''Prover'' 'а прислать ''Verifier'' 'у формулу <tex>A_i(x_{i+1})</tex>.
 
 
Проверим следующее утверждение: <tex>A_i(0) + A_i(1) = A_{i-1}(r_i)</tex>.
 
Проверим следующее утверждение: <tex>A_i(0) + A_i(1) = A_{i-1}(r_i)</tex>.
  
Строка 61: Строка 60:
 
# <tex>\langle \varphi, k \rangle \notin \#SAT \Rightarrow \forall Prover : P(Verifier^{Prover}(x)) \le 1/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>.
+
#Первый факт следует из построения ''Verifier'' 'а.
 
#По [[Арифметизация булевых формул с кванторами | лемме (2)]], если <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1  A_\phi(x_1, \ldots, x_m)=k</tex>, то условия (*) выполнятются, следовательно существует такой ''Prover'', что <tex>P(Verifier^{Prover}(\langle\phi,k\rangle)) = 1</tex>, для любой пары <tex>\langle\phi,k\rangle \in \#SAT</tex>.
 
#По [[Арифметизация булевых формул с кванторами | лемме (2)]], если <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1  A_\phi(x_1, \ldots, x_m)=k</tex>, то условия (*) выполнятются, следовательно существует такой ''Prover'', что <tex>P(Verifier^{Prover}(\langle\phi,k\rangle)) = 1</tex>, для любой пары <tex>\langle\phi,k\rangle \in \#SAT</tex>.
 +
#Пусть количество наборов, удовлетворяющих <tex>\phi</tex>, не равно <tex>k</tex>. Для того, что бы ''Verifier'' вернул ''true'', ''Prover'' 'у необходимо посылать такие <tex>A_i</tex>, чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
 +
:'''Шаг 0'''
 +
:Так как количество наборов, удовлетворяющих <tex>\phi</tex>, не равно <tex>k</tex>, то ''Prover'' не может послать правильное <tex>A_0</tex> – не выполнится условие <tex>A_0(0) + A_0(1) = k</tex>. Поэтому он посылает не <tex>A_0</tex>, а некое <tex>\tilde{A}_0</tex>.
 +
:'''Шаг 1'''
 +
:По [[Лемма Шварца-Зиппеля|лемме Шварца-Зиппеля]] <tex>P(A_0(r_1) = \tilde{A}_0(r_1)) \le \frac d p</tex> для некоторого случайно выбранного <tex>r_1</tex>. Тогда <tex>P(A_0(r_1) \ne \tilde{A}_0(r_1)) \ge 1 - \frac d p</tex>, при этом должно выполняться равенство <tex>A_1(0) + A_1(1) = A_0(r_1)</tex>. Значит с вероятностью не меньше, чем <tex>1 - \frac d p</tex>, ''Prover'' отправит ''Verifier'' 'у  <tex>\tilde{A}_1</tex> вместо <tex>A_1</tex>.
 +
:<tex>\ldots</tex>
 +
:'''Шаг 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''.
 +
 +
 
}}
 
}}
  

Версия 20:18, 1 июня 2012

Определение:
[math]\#SAT=\{\langle \varphi, k \rangle | \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 \iff \langle\phi,k\rangle \in \#SAT[/math].
Доказательство:
[math]\triangleright[/math]
Следует из леммы (1).
[math]\triangleleft[/math]


Лемма (2):
[math]\#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 \#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

Запросим у Prover'а такое простое число [math]p[/math], что [math]max(2^m+1, 3dm) \le p \le 2 \cdot max(2^m+1, 3dm)[/math]. Проверим [math]p[/math] на простоту и на принадлежность заданному промежутку. Как мы знаем, [math]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 Prover : P(Verifier^{Prover}(x)) \ge 2/3[/math].
  3. [math]\langle \varphi, k \rangle \notin \#SAT \Rightarrow \forall Prover : P(Verifier^{Prover}(x)) \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(Verifier^{Prover}(\langle\phi,k\rangle)) = 1[/math], для любой пары [math]\langle\phi,k\rangle \in \#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].
Шаг 1
По лемме Шварца-Зиппеля [math]P(A_0(r_1) = \tilde{A}_0(r_1)) \le \frac d p[/math] для некоторого случайно выбранного [math]r_1[/math]. Тогда [math]P(A_0(r_1) \ne \tilde{A}_0(r_1)) \ge 1 - \frac d p[/math], при этом должно выполняться равенство [math]A_1(0) + A_1(1) = A_0(r_1)[/math]. Значит с вероятностью не меньше, чем [math]1 - \frac d p[/math], Prover отправит Verifier[math]\tilde{A}_1[/math] вместо [math]A_1[/math].
[math]\ldots[/math]
Шаг m
[math]P(A_{m-1}(r_m) \ne \tilde{A}_{m-1}(r_m)) \ge 1 - \frac d p[/math]. Значит с такой вероятностью Verifier получит [math]\tilde{A}_m[/math] вместо [math]A_m[/math]. Но так как на шаге [math]m[/math] Verifier вычисляет [math]A_m[/math] и сравнивает его с полученным от Prover 'а, то в этом случае Verifier вернет false.
[math]\triangleleft[/math]


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

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

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

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