210
правок
Изменения
Нет описания правки
Для доказательства леммы построим программы <tex>V</tex> (<tex> \mathit{Verifier}</tex>) и <tex>P</tex> (<tex>\mathit{Prover}</tex>) из [[Интерактивные протоколы. Класс IP. Класс AM#Класс IP|определения]] класса <tex>\mathrm{IP}</tex>.
Сперва [[Арифметизация булевых формул с кванторами|арифметизуем ]] формулу <tex>\varphi</tex>. Пусть полученный полином <tex>A(x_1, x_2, \ldots, x_m)</tex> имеет степень <tex>d</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(x_1, \ldots, x_m)=k</tex>.
Приступим к описанию [[Интерактивные протоколы. Класс IP. Класс AM|интерактивного протокола]].
'''Шаг 0'''
Докажем теперь, что построенный таким образом интерактивны протокол — корректный. Для этого нужно доказать следующие утверждения:
# Построенный <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> (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> (Soundness).
|statement=<tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
|proof=
Сведём [[Теорема_Бермана_—_Форчуна | язык <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 \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>.
}}
== См. также ==
* [[Интерактивные протоколы. Класс IP. Класс AM]]
* [[Арифметизация булевых формул с кванторами]]
* [[Вероятностные вычисления. Вероятностная машина Тьюринга]]
* [[Теорема Бермана — Форчуна]]
[[Категория: Теория сложности]]
[[Категория: Вероятностные сложностные классы]]
[[Категория: Интерактивные протоколы]]
