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