69
правок
Изменения
Новая страница: «{{Теорема |author=Карп — Липтон |statement= Если <tex>NP \subset P/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex> |proof= Так как <tex>...»
{{Теорема
|author=Карп — Липтон
|statement=
Если <tex>NP \subset P/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>
|proof=
Так как <tex>NP \subset P/poly</tex>, то <tex>\forall n</tex> <tex>\exists </tex> схема полиномиального размера <tex> C_n</tex>, такая что <tex>C_{|x|}(x) = x \in SAT</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>. Тогда определение языка <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>.
}}
|author=Карп — Липтон
|statement=
Если <tex>NP \subset P/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>
|proof=
Так как <tex>NP \subset P/poly</tex>, то <tex>\forall n</tex> <tex>\exists </tex> схема полиномиального размера <tex> C_n</tex>, такая что <tex>C_{|x|}(x) = x \in SAT</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>. Тогда определение языка <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>.
}}
