Что: | Лекция |
Когда: | Вторник, 28 февраля 2012, 18:30–20:05 |
Где: | ПОМИ РАН |
Оракульные вычисления. Полиномиальная иерархия. Полнота задачи \( QBF_k \). Теоремы о коллапсе. Семейства схем полиномиального размера. Коллапс полиномиальной иерархии как следствие \( NP\subseteq P/poly \). Языки во втором уровне полиномиальной иерархии, не имеющие схем фиксированного полиномиального размера