Теорема Карпа-Липтона — различия между версиями
(Новая страница: «== Формулировка == '''Теорема Карпа-Липтона''' <tex>NP \in P/poly</tex> то <tex>sigma2=pi2</tex> == Доказательство …») |
(→Формулировка) |
||
| Строка 2: | Строка 2: | ||
'''Теорема Карпа-Липтона''' | '''Теорема Карпа-Липтона''' | ||
| − | <tex>NP \in P/poly</tex> то <tex> | + | <tex>NP \in P/poly</tex> то <tex>\Sigma_2=\Pi_2</tex> |
== Доказательство == | == Доказательство == | ||
Версия 12:28, 15 апреля 2010
Формулировка
Теорема Карпа-Липтона
то
