editor
143
правки
Изменения
→Сложность по памяти, классы PS, L, NL, coNL
*[[Теорема Сэвича. Совпадение классов NPS и PS]]
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
*[[Классы L, NL, coNL. ]]*[[NL-полнота задачи о достижимости]]*[[Теорема Иммермана]]
=== Полиномиальная иерархия ===
