Изменения

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

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

20 байт добавлено, 15:02, 3 июня 2010
Нет описания правки
Внутри будем проверять используемый набор
<tex>\forall{\varphi{}} (C_{|\varphi{}|}(\varphi{})=0 \Rightarrow \forall{x} \varphi(x)=0) </tex>
<tex>(C_{|\varphi{}|}(\varphi{})=1 \Rightarrow \varphi{}|_{x_1=0} \in SAT или \varphi{}|_{x_1=1} \in SAT)</tex>
Diniska
33
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/1454»

Навигация