Изменения
Нет описания правки
== Доказательство ==
Пусть есть логические схемы для <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.
