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

3 сентября

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

10 сентября

Подсчет количества операций в алгоритме Эвклида нахождения НОД
натуральных чисел.

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

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

17 сентября

Вероятностные машины Тьюринга (два равносильных определения).
Определение вычисления данной функции с ошибкой не более $\epsilon$.
Классы FBPP и BPP. Независимость этих классов от разрешенной
вероятности ошибки.

Вероятностный алгоритм Миллера—Рабина распознавания простоты
данного числа.

24 сентября

Доказательство корректности алгоритма Миллера—Рабина.
Полиномиальный алгоритм извлечения корня данной степени.

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

1 октября

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

8 октября

NP-представления и класс NP.
Примеры языков из класса NP.
Сводимость Карпа и основные ее свойства.
Сводимость задачи КЛИКА к задаче НЕЗАВИСИМОЕ МНОЖЕСТВО,
сводимость последней задачи к задаче ВЕРШИННОЕ ПОКРЫТИЕ,
сводимость задачи о выполнимости КНФ к задаче ЦЛП и
сводимость задачи 4-КНФ к задаче 3-КНФ.

15 октября

Классы PSPACE и EXP.
Включение класса NP в класс PSPACE
и класса PSPACE в класс EXP.

Теорема Кука-Левина о NP-полноте задачи выполнимости
схем из функциональных элементов.
NP-полнота задачи о выполнимости 3-КНФ.
NP-полнота задачи КЛИКА.
NP-полнота задачи о вершинном покрытии.

22 октября

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

29 октября

Построение сильно односторонней функции
исходя из слабо односторонней.

5 ноября

Частично односторонние функции. Построение
односторонней функции из частично односторонней функции.
Вычислительно неотличимые случайные величины. Их свойства.
Определение генераторов ПСЧ.

12 ноября

Односторонние перестановки. Трудный бит для данной односторонней функции.
Построение генератора, исходя из односторонней перестановки и трудного бита.

19 ноября

Обобщенные перстановки.
Построение генератора, исходя из обобщенной перестановки и трудного бита.
Обратный переход (от генератора к обобщенной перестановке и трудному биту).
Неотличимость случайных величин по Яо.
Эквивалентность неотличимости по Яо и вычислительной неотличимости
(в случае, когда одна из величин равномерно распределена).

26 ноября

Лемма о декодировании списком кода Адамара.
Теорема Левина-Голдрейха о трудном бите для данной односторонней функции.

3 декабря

Доказательство леммы о декодировании списком кода Адамара.

Схемы шифрования с закрытым ключом. Построение схемы шифрования с закрытым
ключом на основе генератора ПСЧ.

10 декабря

Односторонние перестановки с секретом.

Схемы шифрования с открытым ключом. Построение такой схемы на основе
односторонней перестановки с секретом.

17 декабря

Неинтерактивные протоколы привязки к биту. Построение такого
протокола на основе необратимой инъективной функции.

11 февраля

Интерактивные протоколы привязки к биту. Построение такого
протокола на основе генератора ПСЧ.

18 февраля лекции не было!

25 февраля

Протоколы бросания монетки по телефону. Построение такого протокола
на основе протокола привязки к биту.

4 марта

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

11 марта

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

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

18 марта

Лемма о неразглашение информации при последовательном выполнении
неразглашающей стратегии.

25 марта

Схемы аутентификации. Построение схемы аутентификации
на основе необратимости функции Рабина.

1 апреля

Схемы цифровой подписи: общее определение.
Схемы цифровой подписи одного бита.
Схемы одноразовой цифровой подписи сообщения фиксированной длины

8 апреля

Семейства хэш-функций с трудно обнаружимыми коллизиями.
(Свободные от коллизий хэш-функции.)

Схема одноразовой цифровой подписи сообщения произвольной длины
на основе семейства хэш-функций с трудно обнаружимыми коллизиями.

15 апреля

Семейства пар функций с трудно обнаружимыми зацепленями.
Использование таких семейств для пострения
семейств хэш-функций с трудно обнаружимыми коллизиями.

22 апреля

Схема цифровой подписи произвольного количества сообщений
(на основе одноразовой цифровой подписи сообщения любой
длины).

29 апреля

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

6 мая

Интерактивное доказательство с нулевым разглашением
для раскрашиваемости графов.

13 мая

Oblivious transfer (забывающая передача).
Улучшенная перестановка с секретом. Построение забыающей передачи с помощью
улучшенной перестановки с секретом.