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

Определение:

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

Лемма (1):

[math]\#SAT \in \mathrm{IP}[/math].

Лемма (2):

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