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