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

Детерминированные и недетерминированные вычисления, сложность по времени и по памяти

Базовые определения

• Сложностные классы
• Вычисления с оракулом

Классы P и NP, NP-полнота

• Класс P
• Недетерминированные вычисления
• Классы NP и Σ₁
• Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
• NP-полнота BH1N
• Теорема Кука
• Теоремы о временной и емкостной иерархиях
• Теорема Бейкера — Гилла — Соловэя
• Теорема Ладнера
• Теорема Левина
• Теорема Бермана — Форчуна
• Теорема Махэни

Примеры NP-полных языков

• NP-полнота языка CNFSAT
• NP-полнота языка 3SAT
• NP-полнота языка IND (максимальное независимое множество)
• NP-полнота языка VCOVER (минимальное вершинное покрытие)
• NP-полнота языка FACTOR
• NP-полнота языка CLIQUE
• NP-полнота задач о гамильтоновом цикле и пути в графах
• NP-полнота задачи о сумме подмножества
• NP-полнота задачи о рюкзаке
• NP-полнота задачи о раскраске графа

Сложность по памяти, классы PS, L, NL, coNL, EXP, NEXP

• Класс PS. Связь класса PS с другими классами теории сложности
• Теорема Сэвича. Совпадение классов NPS и PS
• PS-полнота языка верных булевых формул с кванторами (TQBF)
• PS-полнота задачи Generalized geography
• Классы L, NL, coNL
• Полнота относительно L-сведения. NL-полнота. P-полнота
• Теорема Иммермана
• Классы EXP и NEXP

Полиномиальная иерархия

• Классы PH, Σ и Π
• Теоремы о коллапсе полиномиальной иерархии

Схемная сложность

• Схемная сложность и класс P/poly
• Теорема Карпа — Липтона
• Классы NC и AC
• Теорема о непринадлежности XOR классу AC⁰

Вероятностные сложностные классы

Основные классы

• Вероятностные вычисления. Вероятностная машина Тьюринга
• Классы RP и coRP
• Класс ZPP
• Классы BPP и PP
• Соотношение вероятностных классов
• Лемма Шварца-Зиппеля
• Теорема Лаутемана
• Теорема Валианта-Вазирани

Интерактивные протоколы

• Интерактивные протоколы. Класс IP. Класс AM
• Арифметизация булевых формул с кванторами
• Теорема о соотношении coNP и IP
• Теорема Шамира
• Семейство универсальных попарно независимых хеш-функций
• Протокол Голдвассер-Сипсера для оценки размера множества

Probabilistically checkable proofs

• PCP-система
• Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации
• PCP-теорема

---

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