Изменения
→Детерминированные и недетерминированные вычисления, сложность по времени и по памяти
*[[Классы NP, coNP, Σ₁, Π₁]]
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Сведение по Куку задачи факторизации к языку из NP]]
*[[NP-полнота BH1N]]
*[[Теорема Кука]]
*[[Классы PH, Σ и Π]]
*[[Теоремы о коллапсе полиномиальной иерархии]]
=== Классы задач подсчета ===
*[[Классы Sharp P, Sharp P-Complete|Классы #P, #P-Complete]]
== Схемная сложность ==