Изменения
→Детерминированные и недетерминированные вычисления, сложность по времени и по памяти
*[[Класс P]]
*[[Недетерминированные вычисления]]
*[[Классы NP и , coNP, Σ₁, Π₁]]
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Сведение по Куку задачи факторизации к языку из NP]]
*[[NP-полнота BH1N]]
*[[Теорема Кука]]
* [[NP-полнота языка IND (максимальное независимое множество)]]
* [[NP-полнота языка VCOVER (минимальное вершинное покрытие)]]
* [[NP-полнота языка CLIQUE]]
* [[NP-полнота задач о гамильтоновом цикле и пути в графах]]
* [[NP-полнота задачи о рюкзаке]]
* [[NP-полнота задачи о раскраске графа]]
* [[NP-полнота игры Тетрис]]
=== Сложность по памяти, классы PS, L, NL, coNL, EXP, NEXP ===
*[[Классы PH, Σ и Π]]
*[[Теоремы о коллапсе полиномиальной иерархии]]
=== Классы задач подсчета ===
*[[Классы Sharp P, Sharp P-Complete|Классы #P, #P-Complete]]
== Схемная сложность ==
*[[Классы BPP и PP]]
*[[Соотношение вероятностных классов]]
*[[Лемма Шварца-Зиппеля]]
*[[Теорема Лаутемана]]
*[[Теорема Валианта-Вазирани]]
=== Интерактивные протоколы ===
*[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]]
*[[PCP-теорема]]
----
[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.
