211
правок
Изменения
м
Нет описания правки
{{Определение
|definition=
<tex>\mathrm{\#SAT}=\{\langle \varphi, k \rangle \bigm| \varphi</tex> имеет ровно <tex>k</tex> удовлетворяющих наборов <tex>\}</tex>.
}}
{{Лемма
|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>.
|proof=Следует из [[Арифметизация булевых формул с кванторами | леммы (1)]].
}}
{{Лемма
|about=2
|statement=<tex>\mathrm{\#SAT } \in \mathrm{IP}</tex>.
|proof=
Для доказательства леммы построим программы ''Verifier'' и ''Prover'' из [[Интерактивные протоколы. Класс IP. Класс AM#Класс IP|определения]] класса <tex>\mathrm{IP}</tex>.
Сперва арифметизуем формулу <tex>\phi</tex>. Пусть полученный полином <tex>A(x_1, x_2, ..., 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>.
Приступим к описанию ''Verifier'''а.
#Первый факт следует из построения ''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 \mathrm{\#SAT}</tex>.
#Пусть количество наборов, удовлетворяющих <tex>\phi</tex>, не равно <tex>k</tex>. Для того, что бы ''Verifier'' вернул '''true''', ''Prover'' 'у необходимо посылать такие <tex>A_i</tex>, чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
:'''Шаг 0'''
|statement=<tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
|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>\phi \in \mathrm{TAUT } \Leftrightarrow \langle \phi, 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>.
}}
[[Категория: Теория сложности]]
