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

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

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

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

1. Сложностные классы (3)
   1. Убрать пункт История
   2. Прафильно раставить тех
   3. Сделать отсылку к теорию вычислимости
   4. Сформулировать определения в терминах МТ (смотри трешовую версию)
   5. Категории
   6. См. также, Источники информации
   7. Возможно добавить ещё чуть-чуть информации с википедии или откуда-нибудь
   8. Интервики
2. Вычисления с оракулом (1)
   1. Добавить различные определения сведения, в том числе из трешовой версии
   2. Отформатировать по правилам

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

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

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

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

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

• Классы 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-теорема