Участник:Shersh/Тикеты к 6ому терму

Тикеты подаются в формате X-Y-Z или X.Y.Z.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Probabilistically checkable proofs

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