Изменения

*[[Классы NP, coNP, Σ₁, Π₁]]

*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]

*[[NP-полнота BH1N]]

*[[Теорема Кука]]

* [[NP-полнота языка IND (максимальное независимое множество)]]

* [[NP-полнота языка VCOVER (минимальное вершинное покрытие)]]

* [[NP-полнота языка CLIQUE]]

* [[NP-полнота задач о гамильтоновом цикле и пути в графах]]

*[[Классы PH, Σ и Π]]

*[[Теоремы о коллапсе полиномиальной иерархии]]

== Схемная сложность ==

*[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]]

*[[PCP-теорема]]

----

[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.