Изменения

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

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

151 байт добавлено, 13:36, 15 апреля 2010
Доказательство
для любого 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
C_m-1(fi|_x1=1)=0 =>fi|_x1=0(x2)=0
C_m-1(fi|x1=0) галочка C_m-1(fi|x1=1)
 
Получаем что L\in \Sigma_2
Теорема доказана
Анонимный участник

Навигация