3622
правки
Изменения
→1. Детерминированные и недетерминированные вычисления, сложность по времени и по памяти
*[[NP-полнота BH1N]]
*[[Теорема Кука]]
*[[Теоремы о временной и емкостной иерархиях]]
*[[Теорема Бейкера — Гилла — Соловэя]]
*[[Теорема Махэни]]
=== 3. [[Примеры NP-полных языков]] ====== 4. Сложность по памяти, классы PS, L, NL, coNL ===
*[[Класс PS. Связь класса PS с другими классами теории сложности]]
*[[Теорема Сэвича. Совпадение классов NPS и PS]]
*[[Теорема Иммермана]]
=== 45. Полиномиальная иерархия ===
*[[Классы PH, Σ и Π]]
*[[Теоремы о коллапсе полиномиальной иерархии]]
