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