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