211
правок
Изменения
м
Нет описания правки
<tex>\#SAT=\{\langle \varphi, k \rangle | \varphi</tex> имеет ровно <tex>k</tex> удовлетворяющих наборов <tex>\}</tex>.
}}
Введём понятие арифмитизации булевых формул. Пусть нам дана формула <tex>\phi(x_1 \ldots x_n)</tex>. Сделаем следующие преобразования и получим формулу <tex>A_\phi(x_1, x_2, \ldots, x_n)</tex>:
# <tex> x_i \to x_i</tex>;
# <tex> \lnot x \to 1 - x</tex>;
# <tex>\Phi \land \Psi \to A_\Phi \cdot A_\Psi</tex>;
# <tex>\Phi \lor \Psi \to 1 - (1 - A_\Phi) \cdot (1 - A_\Psi)</tex>.
{{Лемма
|about=1
|statement=<tex>\phi(x_1 \ldots x_n) = A_\phi(x_1, \ldots, x_n)</tex>.
|proof=
}}
{{Лемма
|about=2
|statement=<tex>\sum\limits_{x_1,\ldots, x_n} A_\phi(x_1, \ldots, x_n)=k \iff \langle\phi,k\rangle \in \#SAT</tex>.
|proof=Следует из леммы (1).
}}
{{Лемма
|about=3
|statement=<tex>\#SAT \in \mathrm{IP}</tex>.
|proof=
{{Лемма
|about=24
|statement=<tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
|proof=
Очевидно, что <tex>\phi \in TAUT \iff \langle \phi, 2^k \rangle \in \#SAT</tex>.
По лемме (13) <tex>\#SAT \in \mathrm{IP}</tex>. Тогда <tex>TAUT \in \mathrm{IP}</tex>. Так как <tex>TAUT \in \mathrm{coNPC}</tex>, то <tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
}}
[[Категория: Теория сложности]]
