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

Материал из Викиконспекты

Версия от 12:28, 15 апреля 2010; 192.168.0.2 (обсуждение) (→‎Формулировка)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

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

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

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Карпа-Липтона&oldid=802»