Изменения

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

Теорема Лаутемана

140 байт добавлено, 22:34, 8 апреля 2010
Формулировка
==Формулировка==
Класс '''Теорема Лаутемана''' (Sipser–Lautemann theorem или Sipser–Gács–Lautemann theorem) утверждает, что класс [[Класс BPP | BPP]] содержится в классах [[Классы Sigma_i и Pi_i|<math>\Sigma_2</math> и <math>\Pi_2</math>]] [[Полиномиальная иерархия | полиномиальной иерархии]].
==Доказательство==
109
правок

Навигация