3622
правки
Изменения
→Сложность по памяти, классы PS, L, NL, coNL: раздел обновлён
* [[NP-полнота задачи о раскраске графа]]
=== Сложность по памяти, классы PS, L, NL, coNL , EXP, NEXP ===
*[[Класс PS. Связь класса PS с другими классами теории сложности]]
*[[Теорема Сэвича. Совпадение классов NPS и PS]]
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
*[[PS-полнота задачи Generalized geography]]
*[[Классы L, NL, coNL]]
*[[Полнота относительно L-сведения. NL-полнота. P-полнота]]
*[[Теорема Иммермана]]
*[[Классы EXP и NEXP]]
=== Полиномиальная иерархия ===
