Изменения

Если <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>

Вот когда подставим x1=0 нужно будет использовать(получится Рассмотрим минимальную неправильную схему. Тогда на той формуле, на которой эта схема неправильна, по предположению, что все более короткая короткие формулы правильны,эта формула) и используем для проверки логическую схему более короткую распознается схемами с меньшим числом входов. Если она выдает 1 то мы опять подставляем либо Поэтому обе скобки будут 0 либо 1 и так далеемы не узнаем набор схем. Развернем формулу до конца. Это правильная проверка причем за полином

Если <tex>C\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>SATC_{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 а на самом деле формула не удавлетворима то обе скобки работать не будут.

Рассмотрим минимальную схему которая неправильна, тогда на той формуле, на которой эта схема неправильна. По предположениюВторой вариант был угадать не только булевы схемы для сат но и те схемы, что все более короткие формулы правильны,эта формула распознается схемами с меньшим числом входов. Поэтому эта и эта будут 0 и мы не узнаем набор схем. Можно попробовать развернуть формулу до концакоторые выдают правильные значения. Видимо это будет выглядеть так

Получаем что <texmath> L\forall{in \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> <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})Sigma_2</texmath> И рекурсивно вызываемся от того из них которое равно 1. Ту же самую формулу но записываем от того из них которое равно 1 (это же предикат но для того из них фи при х1= для которого труе)Второй вариант был угадать не только будевы схемы для сат но и те которые выдают нам правильные значения