City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Полиномиальная иерархия
Foundations of computability and complexity theory

What: Lecture
When: Wednesday, 21 November 2012, 18:30–19:50
Where: ПОМИ РАН

Description

Замкнутость классов NSpace[s(n)] относительно дополнения. Полиномиальная иерархия. Простейшие свойства, полные задачи в \(\Sigma_i^P\) и в \(\Pi_i^P\). Оракульное определение полиномиальной иерархии.

Video