Изменения
Нет описания правки
Пусть есть логические схемы для <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 закодировано есть ли доказательство(имеется разложение) или нет. И причем размер этой логической схемы не больше чем какой то полином от n. Но мы не утверждаем, что можем как то конструктивно их построить. Если бы мы могли за полином их построить, то это бы означало, что сат2=п2, что P=NP.
Итак, что это означает, рассмотрим, это означает на самом деле что для любого n (зафиксируем n)
