Изменения

Теория сложности

1356 байт добавлено, 20:03, 4 апреля 2012

Добавлены темы первой волны

[[Категория: Теория сложности]]

*[[Сложностные классы. Вычисления с оракулом]]

*[[Класс P]]

*[[Недетерминированные вычисления. Классы NP и Σ₁]]

*[[Сведение по Карпу. Трудные и полные задачи]]

*[[Примеры NP-полных языков. Теорема Кука]]

*[[Теоремы о временной и емкостной иерархиях]]

*[[Теорема Бейкера — Гилла — Соловэя]]

*[[Теорема Ладнера]]

*[[Теорема Левина]]

*[[Теорема Махэни (лайт)]]

*[[Теорема Махэни]]

*[[Класс PS. Теорема Сэвича. Совпадение классов NPS и PS]]

*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]

*[[Классы L, NL, coNL. NL-полнота задачи о достижимости]]

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

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

*[[Схемная сложность и класс P/poly]]

*[[Теорема Карпа — Липтона]]

*[[Классы NC и AC]]

*[[Теорема о не принадлежности XOR классу AC⁰]]

editor

177

правок