City: Saint Petersburg Novosibirsk Kazan Language: Русский English
What: Lecture
When: Tuesday, 28 February 2012, 18:30–20:05
Where: ПОМИ РАН

Description

Оракульные вычисления. Полиномиальная иерархия. Полнота задачи \( QBF_k \). Теоремы о коллапсе. Семейства схем полиномиального размера. Коллапс полиномиальной иерархии как следствие \( NP\subseteq P/poly \). Языки во втором уровне полиномиальной иерархии, не имеющие схем фиксированного полиномиального размера

Video