Изменения

Перейти к: навигация, поиск

Теорема Карпа-Липтона

71 байт добавлено, 15:04, 15 апреля 2010
→‎Доказательство
Внутри будем проверять используемый набор
для любого fi <tex>\forall{\varphi{}} (С_{|fi\varphi{}|}(fi\varphi{})=0 => для любого \Rightarrow \forall{x fi} \varphi(x)=0) (C_{|fi\varphi{}|}(fi\varphi{})=1 => fi\Rightarrow \varphi{}|_x1_{x_1=0 } \in SAT или fi\varphi{}|_x1_{x_1=1 } \in SAT)</tex>
Если C решает SAT то все хорошо, если нет то зафиксируем формулу на которой не решает. Если выдаст 0 а должна выдать 1 то первое не удолветворяет, если наоборот то обе не удовлетворяет.
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/856»

Навигация