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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 3 участников)
Строка 1: Строка 1:
 +
== Подготовка к доказательству ==
 +
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>\mathrm{\#SAT}=\{\langle \varphi, k \rangle \bigm| \varphi</tex> имеет ровно <tex>k</tex> удовлетворяющих наборов <tex>\}</tex>.
+
<tex>\mathrm{\#SAT}=\{\langle \varphi, k \rangle \mid \varphi</tex> {{---}} [[Определение_булевой_функции | булева формула]], которая имеет ровно <tex>k</tex> удовлетворяющих наборов <tex>\}</tex>.
 
}}
 
}}
  
Строка 7: Строка 9:
 
{{Лемма
 
{{Лемма
 
|about=1
 
|about=1
|statement=<tex>\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}</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>.
 
|proof=Следует из [[Арифметизация булевых формул с кванторами | леммы (1)]].
 
|proof=Следует из [[Арифметизация булевых формул с кванторами | леммы (1)]].
 
}}
 
}}
Строка 16: Строка 18:
 
|statement=<tex>\mathrm{\#SAT} \in \mathrm{IP}</tex>.
 
|statement=<tex>\mathrm{\#SAT} \in \mathrm{IP}</tex>.
 
|proof=
 
|proof=
Для доказательства леммы построим программы <tex>\mathit{Verifier}</tex> и <tex>\mathit{Prover}</tex> из [[Интерактивные протоколы. Класс IP. Класс AM#Класс IP|определения]] класса <tex>\mathrm{IP}</tex>.
 
  
Сперва арифметизуем формулу <tex>\phi</tex>. Пусть полученный полином <tex>A(x_1, x_2, ..., x_m)</tex> имеет степень <tex>d</tex>.
+
Сперва арифметизуем формулу <tex>\varphi</tex>. Пусть полученный полином <tex>A_\varphi(x_1, x_2, \ldots, x_m)</tex> имеет степень <tex>d</tex>.
  
По лемме (1) вместо условия <tex>\langle \phi, k \rangle \in \mathrm{\#SAT}</tex>, можно проверять условие <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1  A_\phi(x_1, \ldots, x_m)=k</tex>.
+
Для доказательства леммы построим программы <tex>V</tex> (<tex> \mathrm{Verifier}</tex>) и <tex>P</tex> (<tex>\mathrm{Prover}</tex>) из [[Интерактивные протоколы. Класс IP. Класс AM#Класс IP|определения]] класса <tex>\mathrm{IP}</tex>.
  
Приступим к описанию <tex>\mathit{Verifier}</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'''
+
Приступим к описанию [[Интерактивные протоколы. Класс IP. Класс AM|интерактивного протокола]].
  
Если <tex>d=0</tex> или <tex>m=0</tex>, то <tex>\mathit{Verifier}</tex> может проверить указанное выше условие сам и вернуть соответствующий результат.
+
; '''Шаг 0'''
Иначе запросим у <tex>\mathit{Prover}</tex>такое простое число <tex>p</tex>, что <tex>3dm \le p \le 6dm</tex> (такое <tex>p</tex> существует в силу [http://ru.wikipedia.org/wiki/Постулат_Бертрана постулата Бертрана]).  
+
:Если <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>p</tex> на простоту и на принадлежность заданному промежутку. Как мы [[Класс P#Примеры задач и языков из P|знаем]], <tex>\mathrm{Primes} \in \mathrm{P}</tex>, следовательно на эти операции у <tex>\mathit{Verifier}</tex>уйдёт полиномиальное от размера входа время.
 
  
Далее будем проводить все вычисления модулю <tex>p</tex>.
+
:Далее будем проводить все вычисления по модулю <tex>p</tex>, то есть над конечным [[Определение поля и подполя, изоморфизмы полей | полем ]] <tex> \mathbb{F}_{p} </tex>, что не позволяет числам становиться слишком большими и упрощает анализ.
  
Попросим <tex>\mathit{Prover}</tex> прислать <tex>\mathit{Verifier}</tex>формулу <tex>A_0(x_1)= \sum\limits_{x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A(x_1, x_2, ..., x_m)</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_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>A_0(x_1)</tex> будет полином от длины входа <tex>\mathit{Verifier}</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>A_0(0) + A_0(1) = k</tex> (*) (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, <tex>\mathit{Verifier}</tex> продолжает свою работу, иначе он прекращает свою работу и возвращет '''false''').
+
:Проверим следующее утверждение: <tex>A_0(0) + A_0(1) = k</tex> (*) (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, <tex>V</tex> продолжает свою работу, иначе он прекращает свою работу и возвращет '''false''').
  
'''Шаг i'''
+
; '''Шаг i'''
 +
:Пусть <tex>r_i = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace</tex>. Отправим <tex>r_i</tex> программе <tex>P</tex>.
  
Пусть <tex>r_i = random(0..p-1)</tex>. Отправим <tex>r_i</tex> программе <tex>\mathit{Prover}</tex>.
+
:Попросим <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>\mathit{Prover}</tex> 'а прислать <tex>\mathit{Verifier}</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}, ..., 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>A_i(0) + A_i(1) = A_{i-1}(r_i)</tex> (*).  
+
:Попросим программу <tex>P</tex> прислать <tex>V</tex> значение <tex>A_m()= A_\varphi(r_1, r_2, \ldots, r_m)</tex>.
  
'''Шаг m'''
+
:Проверим следующее утверждение: <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>.
  
Пусть <tex>r_m = random(0..p-1)</tex>. Отправим <tex>r_m</tex> программе <tex>\mathit{Prover}</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]]).
  
Попросим программу <tex>\mathit{Prover}</tex> прислать <tex>\mathit{Verifier}</tex>'у значение <tex>A_m()= A(r_1, r_2, ..., r_m)</tex>.
+
Докажем эти утверждения.
 
 
Проверим следующее утверждение: <tex>A_m() = A_{m-1}(r_m)</tex> (*).
 
А также сами подставим <tex>r_1, r_2, ..., r_m</tex> в <tex>A(x_1, x_2, ..., x_m)</tex> и проверим правильность присланного значения <tex>A_m()</tex>.
 
  
Возвращаем '''true'''.
+
#Первый факт следует из построения <tex>V</tex>.
 +
#По [[Арифметизация булевых формул с кванторами | лемме (2)]], если <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1  A_\varphi(x_1, \ldots, x_m)=k</tex>, то условия (*) выполняются, а значит, по построению протокола, существует такой <tex>P</tex>, что <tex>\mathbb{P}(V_{P}(\langle\varphi,k\rangle) = 1) = 1</tex>, для любой пары <tex>\langle\varphi,k\rangle \in \mathrm{\#SAT}</tex>.
 +
#Пусть количество наборов, удовлетворяющих <tex>\varphi</tex>, не равно <tex>k</tex>. Для того, чтобы <tex>V</tex> вернул '''true''', <tex>P</tex> должен посылать такие <tex>A_i</tex>, чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
 +
::;'''Шаг 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>.
 +
::;'''Шаг 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>.
 +
::;'''Шаг m'''
 +
:::Так как на последнем шаге <tex>V</tex> сверяет полученное от <tex>P</tex> значение с непосредственно вычисленным, слово будет допущено только в том случае, когда <tex>P</tex> смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
  
Докажем теперь, что построенный таким образом <tex>\mathit{Verifier}</tex> — корректный. Для этого нужно доказать следующие утверждения:
+
:::Вычислим вероятность того, что хотя бы раз корень был угадан.
# Построенный <tex>\mathit{Verifier}</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>\langle \varphi, k \rangle \in \mathrm{\#SAT} \Rightarrow \exists \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \ge 2/3</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>\langle \varphi, k \rangle \notin \mathrm{\#SAT} \Rightarrow \forall \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \le 1/3</tex>.
 
  
Докажем эти утверждения.
+
Таким образом, построенный нами интерактивный протокол корректен, а значит лемма доказана.
 
 
#Первый факт следует из построения <tex>\mathit{Verifier}</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>, то условия (*) выполнятются, следовательно существует такой <tex>\mathit{Prover}</tex>, что <tex>P(\mathit{Verifier^{Prover}}(\langle\phi,k\rangle)) = 1</tex>, для любой пары <tex>\langle\phi,k\rangle \in \mathrm{\#SAT}</tex>.
 
#Пусть количество наборов, удовлетворяющих <tex>\phi</tex>, не равно <tex>k</tex>. Для того, что бы <tex>\mathit{Verifier}</tex> вернул '''true''', <tex>\mathit{Prover}</tex> 'у необходимо посылать такие <tex>A_i</tex>, чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
 
:'''Шаг 0'''
 
:Так как количество наборов, удовлетворяющих <tex>\phi</tex>, не равно <tex>k</tex>, то <tex>\mathit{Prover}</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>\mathit{Prover}</tex> может посылать правильные <tex>A_j</tex> и в итоге <tex>\mathit{Verifier}</tex> вернёт '''true'''.
 
:Для некоторого случайно выбранного <tex>r_i</tex> вероятность того, что <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то есть <tex>r_i</tex> — корень полинома <tex>(A_{i-1} - \tilde{A}_{i-1})(r_i)</tex>, имеющего степень не больше <tex>d</tex>, не превосходит <tex>\frac{d}{p}</tex>.
 
:<tex>\ldots</tex>
 
:'''Шаг m'''
 
:Так как на последнем шаге <tex>\mathit{Verifier}</tex> сверяет полученное от <tex>\mathit{Prover}</tex>'а значение с непосредственно вычисленным, слово будет допущено только в том случае, когда <tex>\mathit{Prover}</tex> смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
 
:
 
:Вычислим вероятность того, что хотя бы раз корень был угадан.
 
:<tex>P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) = 1 - (1 - \frac d p)^m \le 1 - (1 - \frac d {3dm})^m \le \frac 1 3</tex>.
 
:В последнем переходе мы воспользовались [http://ru.wikipedia.org/wiki/Ряд_Тейлора формулой Тейлора] для логарифма и экспоненты, а также тем, что <tex>m>0</tex>.
 
 
 
Таким образом, построенный нами <tex>\mathit{Verifier}</tex> корректен, а значит лемма доказана.
 
 
}}
 
}}
  
 +
== Теорема ==
  
 
{{Теорема
 
{{Теорема
 
|statement=<tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
 
|statement=<tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
 
|proof=
 
|proof=
Сведём язык <tex>\mathrm{TAUT}</tex> к языку <tex>\mathrm{\#SAT}</tex> следующим образом: <tex>\phi \mapsto \langle \phi, 2^k \rangle </tex>, где <tex>k</tex> — количество различных переменных в формуле <tex>\phi</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>\phi \in \mathrm{TAUT} \Leftrightarrow \langle \phi, 2^k \rangle \in \mathrm{\#SAT}</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>.
  
 
По лемме (2) <tex>\mathrm{\#SAT} \in \mathrm{IP}</tex>. Тогда <tex>\mathrm{TAUT} \in \mathrm{IP}</tex>. Так как <tex>\mathrm{TAUT} \in \mathrm{coNPC}</tex>, то <tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
 
По лемме (2) <tex>\mathrm{\#SAT} \in \mathrm{IP}</tex>. Тогда <tex>\mathrm{TAUT} \in \mathrm{IP}</tex>. Так как <tex>\mathrm{TAUT} \in \mathrm{coNPC}</tex>, то <tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
 
}}
 
}}
 +
== См. также ==
 +
* [[Интерактивные протоколы. Класс IP. Класс AM]]
 +
* [[Арифметизация булевых формул с кванторами]]
 +
* [[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 +
* [[Теорема Бермана — Форчуна]]
 +
* [[Классы NP, coNP, Σ₁, Π₁]]
 +
 +
== Примечания ==
 +
<references/>
  
 
[[Категория: Теория сложности]]
 
[[Категория: Теория сложности]]
 +
[[Категория: Вероятностные сложностные классы]]
 +
[[Категория: Интерактивные протоколы]]

Текущая версия на 19:39, 4 сентября 2022

Подготовка к доказательству

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


Лемма (1):
Пусть [math] \varphi [/math] булева формула, а [math] A_\varphi [/math] — её арифметизация. Тогда [math]\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}[/math].
Доказательство:
[math]\triangleright[/math]
Следует из леммы (1).
[math]\triangleleft[/math]


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

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

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

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

Приступим к описанию интерактивного протокола.

Шаг 0
Если [math]d=0[/math] или [math]m=0[/math], то [math]V[/math] может проверить указанное выше условие сам и вернуть соответствующий результат. Иначе запросим у [math]P[/math] такое простое число [math]p[/math], что [math]3dm \leqslant p \leqslant 6dm[/math] (такое [math]p[/math] существует в силу постулата Бертрана[1]. Проверим [math]p[/math] на простоту и на принадлежность заданному промежутку. Как мы знаем, [math]\mathrm{Primes} \in \mathrm{P}[/math], следовательно на эти операции у [math]V[/math] уйдёт полиномиальное от размера входа время.
Далее будем проводить все вычисления по модулю [math]p[/math], то есть над конечным полем [math] \mathbb{F}_{p} [/math], что не позволяет числам становиться слишком большими и упрощает анализ.
Попросим [math]P[/math] прислать [math]V[/math] формулу [math]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)[/math]. Заметим, что размер формулы [math]A_0(x_1)[/math] будет полином от длины входа [math]V[/math], так как [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] (*) (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, [math]V[/math] продолжает свою работу, иначе он прекращает свою работу и возвращет false).
Шаг i
Пусть [math]r_i = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace[/math]. Отправим [math]r_i[/math] программе [math]P[/math].
Попросим [math]P[/math] прислать [math]V[/math] формулу [math]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)[/math].
Проверим следующее утверждение: [math]A_i(0) + A_i(1) = A_{i-1}(r_i)[/math] (*).
Шаг m
Пусть [math]r_m = \mathrm{random} \lbrace0, \ldots, p-1 \rbrace[/math]. Отправим [math]r_m[/math] программе [math]P[/math].
Попросим программу [math]P[/math] прислать [math]V[/math] значение [math]A_m()= A_\varphi(r_1, r_2, \ldots, r_m)[/math].
Проверим следующее утверждение: [math]A_m() = A_{m-1}(r_m)[/math] (*). А также сами подставим [math]r_1, r_2, \ldots, r_m[/math] в [math]A_\varphi(x_1, x_2, \ldots, x_m)[/math] и проверим правильность присланного значения [math]A_m()[/math].
Возвращаем true.

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

  1. Построенный [math]V[/math]вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
  2. [math]\langle \varphi, k \rangle \in \mathrm{\#SAT} \Rightarrow \exists P : \mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \geqslant 2/{3}[/math] (Completeness).
  3. [math]\langle \varphi, k \rangle \notin \mathrm{\#SAT} \Rightarrow \forall P :\mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \leqslant 1/{3}[/math] (Soundness).

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

  1. Первый факт следует из построения [math]V[/math].
  2. По лемме (2), если [math]\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\varphi(x_1, \ldots, x_m)=k[/math], то условия (*) выполняются, а значит, по построению протокола, существует такой [math]P[/math], что [math]\mathbb{P}(V_{P}(\langle\varphi,k\rangle) = 1) = 1[/math], для любой пары [math]\langle\varphi,k\rangle \in \mathrm{\#SAT}[/math].
  3. Пусть количество наборов, удовлетворяющих [math]\varphi[/math], не равно [math]k[/math]. Для того, чтобы [math]V[/math] вернул true, [math]P[/math] должен посылать такие [math]A_i[/math], чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
Шаг 0
Так как количество наборов, удовлетворяющих [math]\varphi[/math], не равно [math]k[/math], то [math]P[/math] не может послать правильное [math]A_0[/math], поскольку в этом случае не выполнится условие [math]A_0(0) + A_0(1) = k[/math]. Поэтому он посылает не [math]A_0[/math], а некое [math]\tilde{A}_0[/math].
Шаг i
Заметим, что если на каком-то шаге [math]A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)[/math], то начиная со следующего шага [math]P[/math] может посылать правильные [math]A_j[/math] и в итоге [math]V[/math] вернёт true.
Для некоторого случайно выбранного [math]r_i[/math] вероятность того, что [math]A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)[/math], не превосходит [math]\dfrac{d}{p}[/math], так как [math]r_i[/math] — корень полинома [math](A_{i-1} - \tilde{A}_{i-1})(r_i)[/math], имеющего степень не больше [math]d[/math], а, по основной теореме алгебры[2], полином имеет ровно [math] d [/math] корней, и [math] r_i \in \lbrace 0, \ldots, p -1 \rbrace[/math].
Шаг m
Так как на последнем шаге [math]V[/math] сверяет полученное от [math]P[/math] значение с непосредственно вычисленным, слово будет допущено только в том случае, когда [math]P[/math] смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
Вычислим вероятность того, что хотя бы раз корень был угадан.
[math]\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 [/math].
Заметим, что функция [math] y(m) = 1 - \left( 1 - \dfrac{1}{3m} \right)^{m}[/math] убывает при [math] m \geqslant \dfrac{1}{3} [/math]. А так как [math] m \geqslant 1 [/math] и [math] y(1) = \dfrac{1}{3} [/math], в итоге получаем, что [math]\mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \leqslant \dfrac{1}{3} [/math].
Таким образом, построенный нами интерактивный протокол корректен, а значит лемма доказана.
[math]\triangleleft[/math]

Теорема

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

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

[math]\varphi \in \mathrm{TAUT} \Leftrightarrow \forall x = (x_1, \ldots, x_k) \varphi(x) = 1 \Leftrightarrow \exists 2^{k} [/math] удовлетворяющих наборов [math] x [/math] для [math] \varphi(x) \Leftrightarrow \langle \varphi, 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]

См. также

Примечания