Изменения

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

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

24 байта добавлено, 14:04, 15 апреля 2010
Доказательство
Пусть есть логические схемы для <tex>NP</tex>. Например <tex>C_1...C_n...</tex> <tex>SAT</tex> который кодирует <tex>i</tex> символов, разрешимых логической схемой <tex>C_i</tex>. Размер <tex>|C_i|\le p(n)</tex>.
Это означает что для фиксированного <tex>n</tex> найдется такая логическая схема <tex>C_n</tex> что для любого
<math>\phivarphi{} (\phivarphi{} \in{} SAT |\phivarphi{}|=n <=> \Leftrightarrow C_n(\phivarphi{})=1)</math>
Существует C_n для любого fi (для любого x fi(x)=0 <=>C_n(fi)=0).
Анонимный участник

Навигация