Изменения

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

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

2 байта добавлено, 19:27, 4 сентября 2022
м
rollbackEdits.php mass rollback
|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>
1632
правки

Навигация