Дневник лекций (осень 2015 года, весна 2016 года)

7 сентября

Одноленточные и многоленточные машины Тьюринга. Время работы и память
как меры сложности. Оценка количества шагов для копирования слова.

Моделирование многолентночных машин Тьюринга на одноленточных МТ.
Полиномиально вычислимые функции и полиномиально разрешимые предикаты.
Классы P и PF.

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

14 сентября

Моделирование РАМ на машинах Тьюринга.

Оценка времени
для алгоритма Евклида и проверки простоты.
Алгоритм быстрого возведения в степень.

Построение разрешимого предиката вне P (кратко).

21 сентября

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

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

28 сентября

Регулярные и расширенные регулярные выражения.

Разрешимость проблемы эквивалентности расширенных регулярных выражений.

Начало доказательства DEXP трудности задачи универстальности расширенных
регулярных выражений.

5 октября

Окончание доказательства DEXP трудности задачи универстальности расширенных
регулярных выражений.

12 октября

Класс NP. NP полные задачи. Примеры. Класс PSCPACE. Включение
NP в EXP. Включение NP в PSCPACE и PSCPACE в EXP.

Доказательство NP полноты задачи CircuitSAT

19 октября

Доказательство NP полноты задач 3-CNF, Clique, VC, SubsetSum, 3-coloring, HamiltonianCycle.

26 октября

Сводимость Кука. NP задачи оптимизации. Сводимость каждой NP задачи оптимизации к некоторой
NP задаче поиска.

NP задачи подсчёта и класс #P. #P полнота задачи подсчета количества выполняющих наборов 3CNF.
#P полнота задачи вычисления перманента булевой матрицы (без доказательства).

2 ноября

Вероятностные алгоритмы. Классы BPP и BPPF. Задача распознавания истинности
алгебраического тождества.

Амплификация.

9 ноября

Схемная сложность. Экспоненциальная верхняя и нижняя оценка схемной сложности.
Классы nuP и P/poly и их совпадение. Несколько слов о попытках доказать, что нижних оценках
схемной сложности явных функций, в частности, NP трудных задач.

Включения P и BPP в P/poly.

16 ноября

Недетерминированные машины Тьюринга и эквивалентное определение NP.

Полиномиальная иерархия. Примеры. Включение в PSPACE. Равенство NP^PSPACE = PSPACE.

Равенство NP^{\Sigma_i}=\Sigma_{i+1} (без доказательства).

23 ноября

Включение P^{\Sigma_i} в \Sigma_{i+1} и \Pi_{i+1}.
Доказательство равенства NP^{\Sigma_i}=\Sigma_{i+1}

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

Полные задачи в классах полиномиальной иерархии.

30 ноября

NPSPACE.
Полиномиальные игры и класс PSPACE.

Теорема Сэвича. PSPACE полнота задачи БФК.

7 декабря

Теорема Иммермана.

Теорема Бейкера — Гилла — Соловея.

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

14 декабря

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

Лемма Вэльянта-Вазирани. Класс RP. Теорема: если UNIQUE-NP включено в RP,
то NP=RP.

15 февраля

Класс ParityP. Замкнутость этого класса относительно сводимости Кука.

Первая лемма Тоды: NP включено в BPP^{ParityP}. Релятивизуемость этой леммы. Следствия:
NP^{ParityP} включено в BPP^{ParityP} и PH^{ParityP} включено в BPP^{ParityP} (по теореме Захоса).

22 февраля лекции не было (предпраздник)

29 февраля

Вторая лемма Тоды: BPP^{ParityP} включено в P^{#P}. Теорема Тоды.

7 марта лекции не было (выходной)

14 марта

Определение классов MA, AM, IP(секр), IP(откр). Включения NP, BPP в AM и MA.
Класс PCP[r,q]. Формулировка PCP-теоремы.
Доказательство принадлежности GNI к IP(секр)[2].

21 марта

Включение IP(секр), IP(откр) в PSPACE.

Амплификация для IP (последовательное и параллельное повторение).

28 марта

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

Попытка доказательтства включения IP(секр) в IP(откр).

4 апреля

Доказательтство включения IP(секр) в IP(откр)

Возможность сделать вероятность принятия единичной для входов из языка.

11 апреля

Лекции не было из-за конференции Сколтеха.

18 апреля

Включение coNP в IP(откр)

Включение PSPACE в IP(откр)

25 апреля

Оракул, относительно которого coNP не включено в IP(секр).

Включение AM[const] в AM.

Включение MA в Sigma2 и AM в Pi2. Если задача об изоморфизме графов NP полна, то
coNP включено в AM и, следовательно, PH=Sigma2=Pi2.

16 мая

PCP-теорема и ее применение к доказательству NP трудности задачи о приближенном
вычислении размера максимальной клики.

Определение класса FPT. Сводимость. Принадлежность классу FPT задачи о вершинном покрытии.
Классы W[i].

23 мая

Доказательство W[1] полноты задач о независимом множестве и weighted-k-CNF.