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

Материал из Викиконспекты
Версия от 12:28, 15 апреля 2010; 192.168.0.2 (обсуждение) (Формулировка)
Перейти к: навигация, поиск

Формулировка

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

[math]NP \in P/poly[/math] то [math]\Sigma_2=\Pi_2[/math]

Доказательство