Участник: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-полнота

1. Класс P (3)
   1. Отформатировать по правилам
2. взяли Недетерминированные вычисления (2)
   1. Отформатировать по правилам
   2. Какую-нибудь разумную структура конспекта создать
   3. Добавить примеров
3. взяли Классы NP и Σ₁ (7)
   1. Отформатировать по правилам
   2. Доказать для некоторых языков из примеров, что они в NP
   3. Ещё простых примеров с доказательством
   4. Добавить определение coNP, примеры языков по возможности с доказательствами
4. Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи (1.5-2)
   1. Отформатировать по правилам
   2. Возможно добавить ещё более простой пример
5. NP-полнота BH1N (1)
   1. Отформатировать по правилам
6. Теорема Кука (2)
   1. Отформатировать по правилам
   2. Сделать табличку красивой
7. Теоремы о временной и емкостной иерархиях (1)
   1. Отформатировать по правилам
8. Теорема Бейкера — Гилла — Соловэя (3)
   1. Отформатировать по правилам
   2. Пояснить подробней все переходы
9. Теорема Ладнера (2)
   1. Отформатировать по правилам
10. Теорема Левина (2)
    1. Отформатировать по правилам
    2. Пояснить неформальный смысл теоремы
    3. Возможно подробней описать
11. Теорема Бермана — Форчуна (2)
    1. Отформатировать по правилам
    2. Добавить структуру конспекту
12. Теорема Махэни (3)
    1. Отформатировать по правилам
    2. Пояснить обозначения в начале

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

1. NP-полнота языка CNFSAT (1)
   1. Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
   2. Оформить правильно
2. NP-полнота языка 3SAT (1)
   1. Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
   2. Оформить правильно
3. NP-полнота языка IND (максимальное независимое множество) (3)
   1. Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
   2. Оформить правильно
   3. Добавить картинку графа-примера
4. NP-полнота языка VCOVER (минимальное вершинное покрытие) (1)
   1. Выпилить из большого конспекта, а в нём сделать ссылку как на основную статью
   2. Оформить правильно
5. NP-полнота языка FACTOR (3)
   1. Оформить правильно
   2. Пояснить происходящее
6. NP-полнота языка CLIQUE (2)
   1. Оформить правильно
   2. Проинлайнить доказательство
7. взяли NP-полнота задач о гамильтоновом цикле и пути в графах (5)
   1. Оформить правильно
   2. Картинки сделать красивыми
8. NP-полнота задачи о сумме подмножества (3)
   1. Оформить правильно
9. NP-полнота задачи о рюкзаке (3)
   1. Оформить правильно
   2. Пояснить подробней
10. NP-полнота задачи о раскраске графа (2)
    1. Оформить правильно

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

1. Класс PS. Связь класса PS с другими классами теории сложности (1)
   1. Отформатировать по правилам
   2. Как-то помёрджить с Класс PS
2. Теорема Сэвича. Совпадение классов NPS и PS (1)
   1. Отформатировать по правилам
3. PS-полнота языка верных булевых формул с кванторами (TQBF) (1)
   1. Отформатировать по правилам
4. PS-полнота задачи Generalized geography (4)
   1. Отформатировать по правилам
   2. Привести примеры, где может быть актуально решать такую задачу
5. Классы L, NL, coNL (3)
   1. Отформатировать по правилам
   2. Добавить больше неформальных пояснений к классам
   3. Добавить ещё несколько утверждений про связи классов L с другими
   4. Помёрджить с этим конспектом и другими из треша: NL-полнота
6. Полнота относительно L-сведения. NL-полнота. P-полнота (2)
   1. Отформатировать по правилам
7. Теорема Иммермана (2)
   1. Отформатировать по правилам
8. Классы EXP и NEXP (4)
   1. Смёрджить два конспекта и отформатировать по правилам: Классы EXP, NEXP. Полнота языков EXP и NEXP, Теорема о связи вопросов EXP=NEXP и P=NP

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

1. Классы PH, Σ и Π (3)
   1. Отформатировать по правилам
   2. Доказать простенькие отношений отсюда: Классы Sigma i и Pi i, Полиномиальная иерархия
2. Теоремы о коллапсе полиномиальной иерархии (2)
   1. Отформатировать по правилам

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-теорема