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

Эта статья находится в разработке!

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

---

Вот сюда можно подсматривать, но злоупотреблять не рекомендуется.