Изменения
Нет описания правки
== Доказательство ==
Пусть есть логические схемы для <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>.
Если <tex>L_1\in{} NP \Rightarrow тоL_1 \le{}_m SAT</tex> по карпу с помощью <tex>f</tex>, т.е. <tex>L=\{x|\forall{y} f(<x,y>)\in{SAT}\}</tex>
Что такое <tex>f(<x,y>)\in subset{SAT }</tex>? <tex>f(<x,y>)\insubset{SAT}</tex> - это значит, что для некоторого набора булевых(логических) схем, это означает выполнимость всего этого набора, если . Если предположить, что набор этих схем нам известен то получится что <tex>L=\{x|\forall{y} C_n(f(<x,y>))=1\}</tex> где <tex>n</tex>- длина входа <tex><x,y></tex>.Нам надо Требуется откуда то взять этот набор. Мы можем его Его можно угадать , используя квантор существует "<tex>\exists{}</tex>снаружи.
Cn он существует по предположению что NP входит в P/poly т.е.
<tex>L=\{x|\exists{C_n}: C_n решает SAT и \forall{y} C_n(f(<x,y>))=1\}</tex>
