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