Дневник лекций 2012/2013 года

17 сентября

Моделирование двухленточных машины Тьюринга на одноленточных машинах.
Сложность копирования и арифметических операций, сложения
для машин Тьюринга.

24 сентября

Равнодоступные адресные машины (РАМ).
Моделирование машин Тьюринга на РАМ и РАМ на
машинах Тьюринга. Класс P полиномиально разрешимых
языков и машинная независимость его определения.

1 октября

Универсальная машина Тьюринга и оценка времени ее работы.
Теорема о иерархии по времени.

Сводимость. Экспоненциальная нижняя оценка времени
распознавания EXP трудных задач.

8 октября

Теорема Фишера—Рабина

22 октября

Окончание доказательства теоремы Фишера—Рабина.

Класс NP, сводимость и понятие NP полной и NP трудной
задачи..

29 октября

Теорема Кука—Левина об NP полноте задачи CIRCUIT-SAT.
NP полнота задачи 3-CNF и CLIQUE.

12 ноября

NP полнота задач НезависимоеМножество, ВершинноеПокрытие,
3-раскраска, СуммаПодмножества, ГамильтоновЦикл и Коммивояжёр.

19 ноября

Сводимость Кука.
Задачи поиска и задачи оптимизации. Их эквивалентность NP полнота задач НезависимоеМножество, ВершинноеПокрытие,
3-раскраска, СуммаПодмножества, ГамильтоновЦикл и Коммивояжёр.

26 ноября

Приближенное решение задач оптимизации: 7/8-аппроксимация MAX3CNF
и 2-аппроксимация минимального вершинного покрытия.
Полиномиальная иерархия. Замкнутость классов относительно
пересечений и объединений. Сводимость по Тьюрингу к \Sigma_k.

3 декабря

Включение полиномиальной иерархии в класс PSPACE.
Характеризация PSPACE с помощью игр. Полные задачи
в классе PSPACE.

10 декабря

Полиномиальные вероятностные алгоритмы. Класс BPP.
Распознавание тождеств. Уменьшение вероятности ошибки (amplification).

17 декабря

Классы nuP и P/poly, их совпадение. Включение BPP в P/poly

Включение BPP в Sigma_2.

Теорема Карпа-Липтона о том, что Включение NP в nuP влечет Sigma_2=Pi_2.

11 февраля

Напоминание пройденного.

Теорема о иерархии для недетерминированных машин.

18 февраля

Недетерминированные машины Тьюринга, окграниченные по памяти. Теорема Сэвича.
Теорема Иммермана.

25 февраля

Задачи подсчета и класс #P. #P полнота
задач подчсета количества выполняющих наборов СФЭ и 3-КНФ,
и количества клик данного размера в данном графе

4 марта

#P полнота
задачи вычисления перманента булевой матрицы.

11 марта

Релятивизуемость. Теорема Бейкера-Гилла-Соловея.

Теорема Захоса: если NP включено в BPP, то и полиномиальная иерархия включена
в BPP.

18 марта

Лемма Вэльянта-Вазирани. Если существует полиномиальный
вероятностный алгоритм с односторонней ошибкой для поиска
единственного свидетеля, то NP=RP.

Лемма Тоды NP включено в BPP^{ParityP}.

25 марта

ParityP^{ParityP}=ParityP

Вторая лемма Тоды: PP^{ParityP} включено в P^{#P}.
Завершение доказательства теоремы Тоды.

1 апреля

Вероятностно проверяемые доказательства. Классы MA и
PCP(r,q). PCP-теорема. NP трудность задачи
c-приближенного вычисления размера максимальной клики
(для любого c).

Интерактивные доказательства с общими и секретными
случайными битами. Интерактивное доказательство неизоморфности
графов.

8 апреля

Включение IP в PSPACE

Последовательное и параллельное повторение интерактивного
доказательства.

15 апреля

Интерактивный протокол с открытыми случайными битами для
GNI

Преобразование протоколов с секретными битами в протоколы
с открытыми битами в общем случае.

22 апреля

Преобразование протоколов с секретными битами в протоколы
с открытыми битами в который доказывающий никогда не ошибается.

IP=PSPACE.

29 апреля

MA включено в AM

IP_public[const]=AM

AM включено в \Pi_2, MA включено в \Sigma_2

6 мая

Теория сложности в среднем. Распределённые задачи и классы
AvgP, HeurP, AvgBPP, HeurBPP.

Сводимость Карпа для распределённых задач.

Полиномиально моделируемое распределение, доминирующее
все полиномиально моделируемые распределения и
полная в (NP,PSamp) задача.

13 мая

Полная в (NP,PISamp) задача.

Сведение любой задачи из (NP,PSamp) к некоторой задаче из
(NP,PISamp).