Дневник лекций 2008/2009 года

8 сентября 2008

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

15 сентября 2008

Моделирование двухленточных машины Тьюринга на одноленточных машинах.

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

Класс FP функций, вычислимых за полиномиальное от длины входа время. Независимость объема этого класса от количества лент. Эквивалентное определение в терминах РАМ. Принадлежность классу FP функции НОД(x,y).

22 сентября 2008

Универсальная двуленточная машина для одноленточных машин.
Оценка замедления времени вычисления функций на универсальной
машине.

Теорема о иерархии.

29 сентября 2008

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

6 октября 2008

Вероятностные алгоритмы. Уменьшение вероятности ошибки.
Классы BPP и FBPP.

Алгоритм Миллера—Рабина проверки простоты натуральных чисел.

13 октября 2008

Схемы из функциональных элементов.
Класс n.u.P. Включение класса P в класс n.u.P

Класс P/poly. Совпадение классов n.u.P и P/poly.
Включение класса BPP в класс P/poly.

20 октября 2008

Класс NP. Сводимость Карпа и ее свойства.
NP-полнота задачи о выполнимости схем из функциональных
элементов. Сводимость некоторых других задач друг к другу.

27 октября 2008

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

NP полнота задач 3-КНФ, 3-РАСКРАСКА.
Полиномиальная разрешимость задачи 2-КНФ.
NP полнота задач КЛИКА, НЕЗАВИСИМОЕ МНОЖЕСТВО, ВЕРШИННОЕ ПОКРЫТИЕ.
NP полнота задач ГАМИЛЬТОНОВ ЦИКЛ и СУММА ПОДМНОЖЕСТВ.

10 ноября 2008

Полиномиальная разрешимость задачи 2-РАСКРАСКА.
NP полнота задач ГАМИЛЬТОНОВ ЦИКЛ, КОММИВОЯЖЕР и СУММА ПОДМНОЖЕСТВ.

Сводимость Тьюринга. Задачи оптимизации.

17 ноября 2008

Полиномиальная разрешимость задачи ЭЙЛЕРОВ ЦИКЛ.
Задачи подсчета и класс Диез-Р. Полнота в классе Диез-Р задач подсчета
количества выполняющих наборов 3-КНФ, количества клик данного размера,
количества 3-раскрасок данного графа.

24 ноября 2008

Полиномиальная разрешимость задачи о существовании совершенного
паросочетания в двудольном графе. Полнота в классе Диез-Р задачи вычисления
перманента булевой матрицы (начало).

1 декабря 2008

Полнота в классе Диез-Р задачи вычисления
перманента булевой матрицы (окончание).

8 декабря 2008

Распределенные задачи. Простые распределенные задачи. Класс DistNP.
Частичный порядок на распределениях.
Сводимость Карпа для распределенных задач. Полная в классе
DistNP распределенная задача.

15 декабря 2008

Вычислительно простые генерируемые распределния.
Dist’NP.

16 февраля 2009

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

2 марта 2009

Существование Dist’NP-полных задач.

16 марта 2009

Существование Dist’NP-полных задач с равномерным распределением на входах
относительно вероятностных сведений.

Dist’NP-полнота задачи о замощении.

23 марта 2009

Сведение задач поиска к задачам распознавания.

30 марта 2009

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

6 апреля 2009

Полиномиальная иерархия. Сигма_i-полные задачи.

Классы PSPACE и EXP. Вложение PSPACE в EXP и вложение классов
полиномиальной иерархии в PSPACE.

Вложение BPP в Сигма_2.

13 апреля 2009

Характеризация класса PSPACE в терминах игр.
Полнота QBF в классе PSPACE.
Принадлежность классу PSPACE задачи об эквивалентности регулярных
выражений.

20 апреля 2009

PSPACE-полнота
задачи об эквивалентности регулярных
выражений.

Класс LOGSPACE. Принадлежность классу LOGSPACE задачи о
достижимости в неориентированных графах.
Принадлежность классу SPACE(log^2 n) задачи о
достижимости в ориентированных графах.

27 апреля 2009

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

Интерактивные доказательства.
Вероятностно проверяемые доказательства.
Классы MA[2], PCP(k,l), IP
(для фиксированной вероятности ошибки).
Теорема PCP(poly(n),poly(n))=NEXP (без доказательства).
Теорема PCP(O(log n),O(log n))=PCP(O(1),O(log n))=NP (без доказательства).

4 мая 2009

Классы AM, AM[k], MA[k].
Последовательное и параллельное повторение
интерактивного доказательства уменьшает вероятность ошибки.

Сведение игры с неполной информацией к игре с полной информацией.
Последовательное и параллельное повторение
интерактивного доказательства с частными датчиками
уменьшает вероятность ошибки.

11 мая 2009

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

18 мая 2009

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

Обозначения MA, AM, MAM, AMA и так далее.
Включение MA в AM. Включение МАМ в АМ.
Включение MA в Pi_2 и МА в Sigma_2.

Интерактивный протокол с открытыми бросаниями
для задачи неизоморфности графов.
Если задача изоморфизма графов является NP-полной,
то PH=\Sigma_2.