Изменения

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

'''Что такое Cn <tex>C_n</tex> Решает <tex>SAT</tex>?'''

<tex>\forall{\varphi{}} (C_{|\varphi{}|}(\varphi{})=0 \Rightarrow \forall{x} \varphi{}(x)=0) \vee{}</tex> <tex>(C_{|\varphi{}|}(\varphi{})=1 \Rightarrow \varphi{}|_{x_1=0} \in SAT или \varphi{}|_{x_1=1} \in SAT)</tex>

Если <tex>C</tex> решает <tex>SAT</ tex> то все хорошо. Если Cn(фи)=0 нет, то для любого x (для любого тут можем использовать) фи(х)=зафиксируем формулу <tex>\varphi{}_0</tex>, которую он не решает. Если на этой формуле выдаст 0Если Cn(фи)=, а должна выдать 1 , то либо фи(ч1=0) принадлежит сат либо фи(х1=1) принадлежит сат тут получается что не удовлетворяет первую часть предыдущего выражения и, значит, не N а длина фиВот когда подставим x1=0 нужно будет использовать(получится более короткая формула) и используем для проверки логическую схему более короткую работать. Если она выдает наоборот выдаст 1 а на самом деле формула не удавлетворима то мы обе скобки не выполнятся и опять подставляем либо 0 либо 1 и так далееформула работать не будет. Это правильная проверка причем за полином

Если <tex>C</tex> решает <tex>SAT</tex> то Рассмотрим минимальную неправильную схему. Тогда на той формуле, на которой эта схема неправильна, по предположению, что все хорошоболее короткие формулы правильны, если нет то зафиксируем формулу которую он не решаетэта формула распознается схемами с меньшим числом входов. Если выдаст Поэтому обе скобки будут 0 а должна выдать 1 то вот эту первую часть не удолветворяет и тут мы не будет работать, если наоборот выдаст 1 а на самом деле формула не удавлетворима то ни эта ни эта не будет работатьузнаем набор схем. Развернем формулу до конца.

Рассмотрим минимальную схему которая неправильна, тогда на той формуле, на которой эта схема неправильна по предположению что все более короткие формулы правильны,эта распознается схемами с меньшим числом входов, поэтому и эта и эта будут <tex> \forall{\varphi{}}: |\varphi{}|=m \forall{x_1}..\forall{x_m} </tex><tex> C_m(\varphi{})=0 \Rightarrow \varphi{(x_1)}=0</tex> иначе <tex> C_{m-1}(\varphi|_{x_1=0})=0 \Rightarrow \varphi|_{x_1=0}(x_2)=0</tex> <tex>C_{m-1}(\varphi{}|_{x_1=1})=0 \Rightarrow \varphi{}|_{x_1=0}(x_2)=0</tex> <tex>C_{m-1}(\varphi{}|{x_1=0 и мы не узнаем набор схем. Можно попробовать развернуть }) \vee{} C_{m-1}(\varphi{}|_{x_1=1})</tex> Далее рекурсивно записываем ту же самую формулу до концаот того из них, которое равно 1. Видимо это будет выглядеть так

<tex> \forall{\varphi{}}: |\varphi{}|=m \forall{x_1}Второй вариант был угадать не только булевы схемы для сат но и те схемы, которые выдают правильные значения..\forall{x_m} если C_m(\varphi{})=0 \Rightarrow \varphi{(x_1)}=0 иначе C_{m-1}(\varphi|_{x_1=0})=0 \Rightarrow \varphi|_{x_1=0}(x_2)=0</tex>

Получаем что <texmath>C_{m-1}(L\varphi{}|_{x_1=1})=0 in \Rightarrow \varphi{}|_{x_1=0}(x_2)=0</tex> <tex>C_{m-1}(\varphi{}|{x_1=0}) \vee{} C_{m-1}(\varphi{}|_{x_1=1})Sigma_2</texmath> И рекурсивно вызываемся от того из них которое равно 1. Ту же самую формулу но записываем от того из них которое равно 1 (это же предикат но для того из них фи при х1= для которого труе)Второй вариант был угадать не только будевы схемы для сат но и те которые выдают нам правильные значения