Дневник лекций 2010/2011 года

16 мая 2011

Применение PCP теоремы к доказательству NP трудности
задачи аппроксимации размера максимальной клики с точностью
до постоянного множителя.

Теория сложности в среднем: полиномиально моделируемые последовательности
распределений, распределенные задачи, классы HeurBPP и (NP,PSamp).
Сведения, сохраняющие HeurBPP и (NP,PSamp) полные задачи.

25 апреля 2011

Почему в определении AM[2] и MA[2] можно считать, что прувер
доказывает верные факты безошибочно.

Доказательство включения PSPACE в AM (окончание).

18 апреля 2011

Включение MA[2] в AM[2].
Совпадение AM[2] и AM[c] для любого c>1.
Включение MA[2] в \Sigma_2 и AM[2] в \Pi_2.

Начало доказательства включения PSPACE в AM.

11 апреля 2011

Еще раз о доказательстве леммы о повторении интерактивного протокола.

Еще раз о IP=AM и увеличение цены игры.

4 апреля 2011

АМ протокол для неизоморфизма графов.

Лемма о параллельном повторении интерактивного протокола.

IP=AM

28 марта 2011

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

Класс АМ (с открытыми бросаниями). Включение IP в PSPACE

21 марта 2011

Универсальный алгоритм поиска Левина.

Интерактивные доказательства. Классы МА, PCP, PCP с доказательством
экспоненциальной длины, IP. Интерактивное доказательство неизоморфности графов.

14 марта 2011

Окончание доказательства теоремы Тоды: PP^{+P} включено в P^{#P}

Теорема Иммермана: NLOGSPACE=coNLOGSPACE.

7 марта 2011

Лекции не было.

28 февраля 2011

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

Теорема Закоса.
Класс +Р и его замкнутость относительно сводимости Кука.
Начало доказательства теоремы Тоды: включение PH в BPP^{+P}.

21 февраля 2011

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

14 февраля 2011

Класс #P задач подсчета. Сведение задач из
#P к языкам из класса РР и обратное сведение.
#P полнота задач подсчета количества выполняющих
присваиваний для булевых схем и 3CNF, подсчета количества
клик в графе и подсчета количества раскрасок графа в 3 цвета.

13 декабря 2010 лекции не было.

6 декабря 2010

Обобщение теоремы Фишера-Рабина на вероятностные машины и
альтернирующие машины.

Теорема Вэльянта-Вазирани.

29 ноября 2010

Теорема об иерархии для NP и других классов
полиномиальной иерархии.

22 ноября 2010

Характеризация класса PSPACE с помощью
полиномиальных игр.
PSPACE полнота БФК.
PSPACE полнота задачи эквивалентности регулярных выражений.
Распознавание s-t-связности на зоне O(\log^2 n)

15 ноября 2010

Класс PSPACE.
Вложение PSPACE в EXPTIME.
Вложение PH в PSPACE.
Полиномиальные игры. Принадлежность PSPACE множетсва выигрышных позиций в
полиномиальной игре.

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

1 ноября 2010

Вне класса NP: полиномиальная иерархия.
Примеры: БФК, жесткие графы, неупрощаемые формулы, единственная наибольшая
клика, размер наибольшей клики.
Полные проблемы в классах полиномиальной иерархии.

Уменьшение вероятности ошибки при повторении. Классы PP, BPP, FBPP, RP.
Включение BPP в P/poly.

25 октября 2010

Алгоритмические проблемы общего вида.
Взаимная сводимость NP задач поиска и NP задач распознавания.
Взаимная сводимость NP задач поиска и задач оптимизации.

Приближенное решение задач оптимизации.
NP трудность задачи нахождения раскраски графа в (4/3-\eps+o(1))\xi(G)
цветов.
Полиномиальный алгоритм 7/8-апроксимации MAX3CNF.

18 октября 2010

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

NP полнота задач Гамильтонов цикла, 3-раскраска, Коммивояжер.

11 октября 2010

NP полнота задачи выполнимости 3-КНФ.
Полиномиальная разрешимость задач 2-КНФ и 2-раскраска.

NP полнота задач Клика, Независимое множество, Вершинное покрытие,
Сумма подмножества.

4 октября 2010

Класс NP. Сводимость Карпа и ее свойства.

NP трудные и NP полные задачи. Теорема Кука — Левина об NP полноте
задачи о выполнимости схем из функциональных элементов.

27 сентября 2010

Класс nuP. Включение P в nuP. Класс P/poly и его совпадение с классом nuP.

Схемы из функциональных элементов.
Верхняя оценка O(n2^n) схемной сложности любой булевой функции
от n переменных. Существование функций схемной сложности 2^n/3n.

20 сентября 2010

Теорема Фишера — Рабина об экспоненциальной нижней оценке
времени распознавания истинности формул первого порядка
в аддитивной группе действительных чисел.

13 сентября 2010

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

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

6 сентября 2010

Моделирование двухленточных машины Тьюринга на одноленточных машинах.
Время, достаточное для копирования, сложения, обращения и распознавания
палиндромов на одноленточных и двухленточных машинах Тьюринга.

Теорема Хэнни-Стирнза о квадратичной нижней оценке времени
решения этих задач на
одноленточных машинах Тьюринга.