Дневник лекций 2014 года
12 сентября 2014
Многоленточные машины Тьюринга. Время и память.
Моделирование многоленточных машин Тьюринга на одноленточных машинах
Тьюринга.
19 сентября 2014
РАМ (равнодоступные адресные машины).
Моделирование многооленточных машин Тьюринга на РАМ.
2 октября 2014
Сложность выполнения арифметических операций на машинах Тьюринга.
Моделирование РАМ на машинах Тьюринга.
Полиномиальные алгоритмы. Полиномиальность алгоритма Эвклида.
Класс P.
9 октября 2014
Теоремы о иерархии по памяти и по времени.
Разделение P и DEXP.
16 октября 2014
Сводимости Карпа и Кука. Примеры. Свойства сводимостей.
23 октября 2014
Теорема Фишера — Рабина. Доказательство (за исключением коротких
формул для выражения натуральных чисел и возведение в степень)
30 октября 2014
Сессия (лекция отменена)
6 ноября 2014
Завершение доказательства: короткие
формулы для выражения натуральных чисел и возведения в степень.
Короткая формула для выражения того, что z есть натуральное число,
двоичная запись которого равна данной строке.
Кратко о классе NP.
13 ноября 2014
Определение класса NP (через наличие свидетеля).
Определение NP трудной и полной задачи.
Теорема Левина — Кука об NP полноте задачи CIRCUIT-SAT.
NP полнота задачи 3-CNF.
20 ноября 2014
NP полнота задач КЛИКА, НЕЗАВИСИМОЕ МНОЖЕСТВО, ВЕРШИННОЕ ПОКРЫТИЕ,
СУММА ПОДМНОЖЕСТВА, 3-РАСКРАСКА, ГАМИЛЬТОНОВ ЦИКЛ, КОММИВОЯЖЁР.
27 ноября 2014
Схемы из функциональных элементов, схемная сложность функций.
Экспоненциальная верхняя оценка сложности любой функции. Экспоненциальная
нижняя оценка сложности некоторых булевых функций.
Класс n.u.P. Включение P в n.u.P.
Вероятностные машины Тьюринга.
4 декабря 2014
Классы BPP и FBPP. Амплификация.
Упрощенный алгоритм Рабина проверки простоты.
Вероятностный алгоритм проверки полиномиальных алгебраических
тождеств.
Включение BPP в nuP,
11 декабря 2014
Полиномиальная иерархия. Полные задачи в классах полиномиальной иерархии
Класс PSPACE. Включение полиномиальной иерархии в PSPACE. Полная задача в PSPACE.
Включение BPP в Сигма-2.