211
правок
Изменения
Новая страница: «{{Определение |definition= <tex>\#SAT=\{\langle \varphi, k \rangle | \varphi</tex> имеет ровно <tex>k</tex> удовлетворяющих н...»
{{Определение
|definition=
<tex>\#SAT=\{\langle \varphi, k \rangle | \varphi</tex> имеет ровно <tex>k</tex> удовлетворяющих наборов <tex>\}</tex>.
}}
{{Лемма
|about=1
|statement=<tex>\#SAT \in \mathrm{IP}</tex>.
|proof=
}}
{{Лемма
|about=2
|statement=<tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
|proof=
Сведём язык <tex>TAUT</tex> к языку <tex>\#SAT</tex> следующим образом: <tex>\phi \mapsto \langle \phi, 2^k \rangle </tex>, где <tex>k</tex> — количество различных переменных в формуле <tex>\phi</tex>.
Очевидно, что <tex>\phi \in TAUT \iff \langle \phi, 2^k \rangle \in \#SAT</tex>.
По лемме (1) <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>.
}}
[[Категория: Теория сложности]]
|definition=
<tex>\#SAT=\{\langle \varphi, k \rangle | \varphi</tex> имеет ровно <tex>k</tex> удовлетворяющих наборов <tex>\}</tex>.
}}
{{Лемма
|about=1
|statement=<tex>\#SAT \in \mathrm{IP}</tex>.
|proof=
}}
{{Лемма
|about=2
|statement=<tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
|proof=
Сведём язык <tex>TAUT</tex> к языку <tex>\#SAT</tex> следующим образом: <tex>\phi \mapsto \langle \phi, 2^k \rangle </tex>, где <tex>k</tex> — количество различных переменных в формуле <tex>\phi</tex>.
Очевидно, что <tex>\phi \in TAUT \iff \langle \phi, 2^k \rangle \in \#SAT</tex>.
По лемме (1) <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>.
}}
[[Категория: Теория сложности]]
