Теорема Карпа-Липтона — различия между версиями
| Строка 16: | Строка 16: | ||
L_1\in NP => L_1 <=SAT по карпу с помощью f, т.е. L={x|для любого y f(<x,y>)\in SAT} | L_1\in NP => L_1 <=SAT по карпу с помощью f, т.е. L={x|для любого y f(<x,y>)\in SAT} | ||
f(<x,y>)\in SAT это значит, что для некоторого набора формул выполняется для всего набора, если предположить, что L={x|для любого y C_n(f(<x,y>))=1} | f(<x,y>)\in SAT это значит, что для некоторого набора формул выполняется для всего набора, если предположить, что L={x|для любого y C_n(f(<x,y>))=1} | ||
| + | |||
| + | Но надо откуда-то взять этот набор. Можно его угадать, используя квантор существует. Добавим его. | ||
| + | Так как NP \in P/poly | ||
| + | L={x|существует C_n: C_n решает SAT и для любого y C_n(f(<x,y>))=1} | ||
| + | Что означает C_n решает SAT? Нужно переписать с квантором для любого. | ||
| + | C_n решает SAT <=> для любого \fi для любого x (если fi(x)=1 то C_n(fi)=1) | ||
| + | |||
| + | Воспользуемся самосведением SAT L={x|существуют C1C2...Cn - набор логических схем для SAT и для любого y C_n(f(<x,y>))=1} | ||
| + | Внутри будем проверять используемый набор | ||
| + | для любого fi (С_|fi|(fi)=0 => для любого x fi(x)=0) (C_|fi|(fi)=1 => fi|_x1=0 \in SAT или fi|_x1=1 \in SAT) | ||
| + | Если C решает SAT то все хорошо, если нет то зафиксируем формулу на которой не решает. Если выдаст 0 а должна выдать 1 то первое не удолветворяет, если наоборот то обе не удовлетворяет. | ||
| + | |||
| + | для любого fi |fi|=m для любого x_1...любого x_m если C_m(fi)=0 => fi(x_1)=0 иначе C_m-1(fi|_x_1=0)=0 => fi|_x1=0(x2)=0 | ||
Версия 13:30, 15 апреля 2010
Формулировка
Теорема Карпа-Липтона
то
Доказательство
Пусть есть логические схемы для NP. Например C_1...C_n... SAT который кодирует i символов, разрешимых логической схемой C_i. Размер |C_i|<=p(n). Это означает что для фиксированного n найдется такая логическая схема C_n что для любого fi (fi \in SAT & |fi|=n <=> C_n(fi)=1) Существует C_n для любого fi (для любого x fi(x)=0 <=>C_n(fi)=0).
Рассмотрим язык L\in Pi_2. Это значит, что x\in L <=> для любого y существует z такой что кси(x,y,x) Рассмотрим L_1={<x,y> | существует z кси(x,y,z)} L_1 \in NP по определению NP L={x|для любого y <x,y>\in L_1} Нужно доказать что L\in \Sigma_1 L_1\in NP => L_1 <=SAT по карпу с помощью f, т.е. L={x|для любого y f(<x,y>)\in SAT} f(<x,y>)\in SAT это значит, что для некоторого набора формул выполняется для всего набора, если предположить, что L={x|для любого y C_n(f(<x,y>))=1}
Но надо откуда-то взять этот набор. Можно его угадать, используя квантор существует. Добавим его. Так как NP \in P/poly L={x|существует C_n: C_n решает SAT и для любого y C_n(f(<x,y>))=1} Что означает C_n решает SAT? Нужно переписать с квантором для любого. C_n решает SAT <=> для любого \fi для любого x (если fi(x)=1 то C_n(fi)=1)
Воспользуемся самосведением SAT L={x|существуют C1C2...Cn - набор логических схем для SAT и для любого y C_n(f(<x,y>))=1} Внутри будем проверять используемый набор для любого fi (С_|fi|(fi)=0 => для любого x fi(x)=0) (C_|fi|(fi)=1 => fi|_x1=0 \in SAT или fi|_x1=1 \in SAT) Если C решает SAT то все хорошо, если нет то зафиксируем формулу на которой не решает. Если выдаст 0 а должна выдать 1 то первое не удолветворяет, если наоборот то обе не удовлетворяет.
для любого fi |fi|=m для любого x_1...любого x_m если C_m(fi)=0 => fi(x_1)=0 иначе C_m-1(fi|_x_1=0)=0 => fi|_x1=0(x2)=0
