Изменения

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

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

*[[Класс P]]

*[[Недетерминированные вычисления]]

*[[Теорема Бермана — Форчуна]]

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

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

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

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

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

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

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

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

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

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

*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]

*[[Классы BPPweak и BPPstrong]]

*[[Уменьшение ошибки в классе RP]]

*[[Теорема Лаутемана]]

*[[Интерактивные протоколы. Класс IP. Класс AM]]

*[[Связь классов IP и AM друг с другом и с другими классами языков]]

*[[Семейство универсальных попарно независимых хеш-функций]]

*[[Протокол Голдвассера-Сипсера для оценки размера множества]]

*[[PCP-система]]

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