Изменения

|author=Карп — , Липтон

Если <tex>NP \subset P/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>.

Так как <tex>NP \subset P/poly</tex>, то для любого <tex>\forall n</tex> <tex>\exists </tex> найдётся схема полиномиального размера <tex> C_n</tex>, такая что <tex>C_{|x|}(x) = \left[x \in SAT\right]</tex>. <br>Тогда <tex>\forall n </tex> <tex>\exists </tex> , найдётся и схема полиномиального размера <tex> D_n</tex>, выдающая на для <tex>x \in SAT</tex> набор значений, удовлетворяющий формулуформуле. <br/>Рассмотрим язык <tex>L \in \Pi_2</tex>, <tex>L = \{z:\forall x </tex> <tex>\exists y </tex> <tex> \phi(x, y, z)\}</tex>. <br/> Рассмотрим формулу <tex>\exists y</tex> <tex>\phi(x, y, z)</tex> как экземпляр задачи <tex>SAT</tex>. <br/>Тогда определение языка <tex>L</tex> можно переписать так: <tex>L=\{z: \forall x</tex> <tex> \phi(x,D_{|x|}(x, z), z)\}</tex>. <br/> Покажем что <tex>\forall x</tex> <tex> \phi(x,D_{|x|}(x, z), z)</tex> <tex>\Leftrightarrow</tex> <tex>\exists D</tex> <tex> \forall x</tex> <tex>\phi(x, D(x, z), z)</tex>. Очевидно , из первого следует второе, так как <tex>\exists D = D_{|z|}</tex>. <br> Если первое ложно, то <tex>\exists x</tex><tex>\forall y</tex> <tex>\phi(x, y, z) = 0</tex>, а значит <tex>\forall D \phi (x, D_{|z|}(x, z), z)</tex>, то есть второе ложно. <br>Итого, язык <tex>L=\{z:\exists D</tex> <tex>\forall x</tex> <tex>\phi(x, D(x, z), z)\}</tex>, значит <tex>L \in \Sigma_2</tex>.