Лемма о соотношении coNP и IP

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
[math]\#SAT=\{\langle \varphi, k \rangle | \varphi[/math] имеет ровно [math]k[/math] удовлетворяющих наборов [math]\}[/math].


Введём понятие арифмитизации булевых формул. Пусть нам дана формула [math]\phi(x_1 \ldots x_n)[/math]. Сделаем следующие преобразования и получим формулу [math]A_\phi(x_1, x_2, \ldots, x_n)[/math]:

  1. [math] x_i \to x_i[/math];
  2. [math] \lnot x \to 1 - x[/math];
  3. [math]\Phi \land \Psi \to A_\Phi \cdot A_\Psi[/math];
  4. [math]\Phi \lor \Psi \to 1 - (1 - A_\Phi) \cdot (1 - A_\Psi)[/math].
Лемма (1):
[math]\phi(x_1 \ldots x_n) = A_\phi(x_1, \ldots, x_n)[/math].
Лемма (2):
[math]\sum\limits_{x_1,\ldots, x_n} A_\phi(x_1, \ldots, x_n)=k \iff \langle\phi,k\rangle \in \#SAT[/math].
Доказательство:
[math]\triangleright[/math]
Следует из леммы (1).
[math]\triangleleft[/math]


Лемма (3):
[math]\#SAT \in \mathrm{IP}[/math].
Лемма (4):
[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].

По лемме (3) [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]