Теорма Савича и следствие о NPSPACE = PSPACE. Полнота TQBF в классе PSPACE. Теорема об иерархии по памяти. Логарифмические по памяти сведения и их свойства. Класс NL, полная задача в нем.