Изменения

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

2 байта добавлено, 01:05, 8 июня 2012

Нет описания правки

|proof=

Пусть нам дана формула <tex>\phi</tex> с <tex>n</tex> переменными.<br>

~~Попобуем~~ Попробуем построить схемы <tex>C_n^1, \ldots, C_n^n</tex>, работающие следующим образом:

*<tex>C_n^1(\phi) = 1 \Leftrightarrow \exists x_2,\ldots, x_n: \phi(1,x_2, \ldots, x_n)=1</tex>;

*<tex> \ldots </tex>

Анонимный участник