Изменения
Нет описания правки
== Доказательство ==
Пусть есть логические схемы для <tex>NP</tex>(любой задаче из NP). Например зафиксируем любую из NP например пусть сат разрешает логическими схемами <tex>SAT : C_1...C_n...</tex>, сат который поддерживает с одним битом разрешается логической схемой с1 сат с двумя переменными логической схемой с2... который кодирует <tex>i</tex> символов, разрешимых логической схемой <tex>C_i</tex>. Размер <tex>|C_i|\le p(n)</tex>.
Это означает что для фиксированного <tex>n</tex> <tex>\exists{}</tex> такая логическая схема <tex>C_n</tex>, что <tex>\forall{}\varphi{} (\varphi{} \in{} SAT |\varphi{}|=n \Leftrightarrow C_n(\varphi{})=1)</tex>
