=== 4. Сложность по памяти, классы PS, L, NL, coNL ===
*#[[Класс PS. Связь класса PS с другими классами теории сложности]](0.5)*## Отформатировать по правилам#[[Теорема Сэвича. Совпадение классов NPS и PS]](1)*## Отформатировать по правилам #[[PS-полнота языка верных булевых формул с кванторами (TQBF)]](1)## Отформатировать по правилам *#[[Классы L, NL, coNL]](3)*## Отформатировать по правилам## Добавить больше неформальных пояснений к классам## Добавить ещё несколько утверждений про связи классов L с другими#[[Полнота относительно L-сведения. NL-полнота. P-полнота]](2)## Отформатировать по правилам*#[[Теорема Иммермана]](2)## Отформатировать по правилам
=== 5. Полиномиальная иерархия ===
