3622
правки
Изменения
проставлены номера разделов
== 1. Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ===== 1. Базовые определения ===
*[[Сложностные классы]]
*[[Вычисления с оракулом]]
=== 2. Классы P и NP, NP-полнота ===
*[[Класс P]]
*[[Недетерминированные вычисления]]
*[[Теорема Махэни]]
=== 3. Сложность по памяти, классы PS, L, NL, coNL ===
*[[Класс PS. Связь класса PS с другими классами теории сложности]]
*[[Теорема Сэвича. Совпадение классов NPS и PS]]
*[[Теорема Иммермана]]
=== 4. Полиномиальная иерархия ===
*[[Классы PH, Σ и Π]]
*[[Теоремы о коллапсе полиномиальной иерархии]]
== 2. Схемная сложность ==
*[[Схемная сложность и класс P/poly]]
*[[Теорема Карпа — Липтона]]
*[[Теорема о непринадлежности XOR классу AC⁰]]
== 3. Вероятностные сложностные классы ===== 1. Основные классы ===
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы RP и coRP]]
*[[Теорема Лаутемана]]
=== 2. Интерактивные протоколы ===
*[[Интерактивные протоколы. Класс IP. Класс AM]]
*[[Арифметизация булевых формул с кванторами]]
*[[Протокол Голдвассер-Сипсера для оценки размера множества]]
=== 3. Probabilistically checkable proofs ===
*[[PCP-система]]
*[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]]
*[[PCP-теорема]]
