Изменения
Нет описания правки
<math>NP \subset P/poly</math> то <math>\Sigma_2=\Pi_2</math>
=== Текст заголовка ===
== Доказательство ==
Итак, это означает, что если зафиксировать <tex>n</tex>, для этого фиксированного <tex>n</tex>
<tex>\exists{C_n}\forall{} формулы \varphi{} (\varphi{} \in{} SAT |\varphi{}|=n \Leftrightarrow C_n(\varphi{})=1)</tex>
<tex> \exists{C_n} \forall{\varphi{}} (\forall{x} \varphi{(x)}=0 \Leftrightarrow C_n(\varphi{})=0)</tex> , где <tex>x</tex> - вход длины <tex>n</tex>
