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

Материал из Викиконспекты
Версия от 12:27, 15 апреля 2010; 192.168.0.2 (обсуждение) (Новая страница: «== Формулировка == '''Теорема Карпа-Липтона''' <tex>NP \in P/poly</tex> то <tex>sigma2=pi2</tex> == Доказательство …»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

[math]NP \in P/poly[/math] то [math]sigma2=pi2[/math]

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

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