Изменения
Нет описания правки
== Доказательство ==
Пусть есть логические схемы для <tex>NP</tex>. Например <tex>C_1...C_n... </tex> <tex>SAT </tex> который кодирует <tex>i </tex> символов, разрешимых логической схемой <tex>C_i</tex>. Размер <tex>|C_i|<=\le p(n)</tex>.
Это означает что для фиксированного n найдется такая логическая схема C_n что для любого fi (fi \in SAT & |fi|=n <=> C_n(fi)=1)
Существует C_n для любого fi (для любого x fi(x)=0 <=>C_n(fi)=0).
