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

2012-06-03T11:18:23Z

176.14.107.192:

{{В разработке}}

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

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

----

[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.

Викиконспекты - Вклад участника [ru]

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