Изменения
Нет описания правки
Пусть есть логические схемы для <tex>NP</tex> (любой задаче из NP).Зафиксируем любую задачу из <tex>NP</tex>. Пусть например <tex>SAT</tex> разрешается логическими схемами <tex> C_1...C_n... </tex> (<tex>SAT</tex> с одним битом разрешается логической схемой <tex>C_1</tex>, <tex>SAT</tex> с двумя переменными логической схемой <tex>C_2</tex> и так далее).
Что значит разрешается логической схемой? Это значит что если на вход логической схеме подать каким-то логичным образом закодированную формулу, то на выходе получется логичным образом в виде 0 и 1 закодированный ответ - имеется разложение или нет. И причем размер этой логической схемы <tex>|C_n|\le p(n) </tex>, где <tex>p</tex> - какой-то полином от <tex>n</tex>.
Итак, что это означает, рассмотрим, это означает на самом деле что для любого n (зафиксируем n)
