Участник:Shersh/Тикеты к 6ому терму
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. Полиномиальная иерархия
2. Схемная сложность
3. Вероятностные сложностные классы
1. Основные классы
- Вероятностные вычисления. Вероятностная машина Тьюринга
- Классы RP и coRP
- Класс ZPP
- Классы BPP и PP
- Соотношение вероятностных классов
- Теорема Лаутемана
2. Интерактивные протоколы
- Интерактивные протоколы. Класс IP. Класс AM
- Арифметизация булевых формул с кванторами
- Теорема о соотношении coNP и IP
- Теорема Шамира
- Семейство универсальных попарно независимых хеш-функций
- Протокол Голдвассер-Сипсера для оценки размера множества
