Равнодоступные адресные машины, меры сложности: количество операций, длина машинного слова, количество использованных регистров. Полиномиальные РАМ (по всем трем мерам сложности).
Полиномиальные алгоритмы нахождения НОД и быстрого возведения в степень по данному модулю.
Одноленточные и многоленточные машины Тьюринга. Время работы и память как меры сложности. Оценка количества шагов для переворачивания слова.
Моделирование РАМ на машинах Тьюринга на РАМ.
Моделирование многолентночных машин на одноленточных.
Моделирование РАМ на машинах Тьюринга.
Классы полиномиально вычислимых функций и полиномиально разрешимых предикатов. Независимость этих классов от вычислительной модели.
Вероятностные алгоритмы. Полиномальные по времени вероятностные алгоритмы (время ограничено полиномом от длины входа при любых исходах бросаний). Определение вычисления с ограниченной ошибкой. Уменьшение вероятности ошибки с помощью повторения. Классы BPP и FBPP.
Вероятностный полиномиальный алгоритм проверки полиномиального тождества.
Схемы из функциональных элементов. Верхняя оценка O(n2^n) схемной сложности любой булевой функции.
Класс nuP. Включение P в nuP.
Класс P/poly и его совпадение с классом nuP. Принадлежность классу Р равносильно наличию алгоритма, который за полиномиальное от n время находит схему, вычисляющую сужение предиката на слова длины n.
Включение BPP в nuP. Обзор известных нижних оценок.
Класс NP. Примеры задач из класса NP. Сводимость Карпа и ее свойства. Определение NP трудной и NP полной задачи.
Теорема Кука-Левина о NP полноте задачи выполнимости схем из функциональных элементов. NP полнота задач 3-КНФ и Клика.
NP полнота задач Антиклика, ВершинноеПокрытие, СуммаПодмножества, 3-раскраска.
Определение слабо и сильно необратимой функции. Односторонние функции. Примеры. Обратимость любой полиномиально вычислимой функции в предположении P=NP.
Теорема Левина и Голдрайха о преобразовании слабо односторонней функции в сильно одностороннюю функцию.
Статистическое расстояние и доступные распределения. Односторонние частичные функции. Примеры предположительно односторонних частичных функций: функция Рабина и функция RSA.
Вычислительная неотличимость последовательностей случайных величин. Генераторы ПСЧ, конечные и бесконечные. Слабая необратимость генераторов. Существование генераторов при условии существования односторонних функций.
Свойства вычислительно неотличимых последовательностей случайных величин.
Трудно вычислимые случайные величины. Трудный бит для односторонней перестановки. Построение генератора на основе трудного бита и односторонней перестановки (или функции, сохраняющей равномерное распределение).
Построение генератора с любой степенью расширения из генератора с минимальной степенью расширения.
Вероятностное декодирование списком кода Адамара. Теорема Левина--Голдрайха о построении труднго бита для данной односторонней перестановки.
Псевдослучайные функции и их построение на основе генератора ПСЧ.
Коллоквиум.
Шифрование с закрытым ключом. Одноразовая схема на основе генератора ПСЧ. Многоразовая схема на основе семейства ПСФ и одноразовой схемы.
Многоразовая схема на основе семейства ПСФ и одноразовой схемы. (Доказательство)
Схемы шифрования с открытым ключом (определение).
Семейства перестановок с секретом. Трудный бит перестановки с секретом. Построение семейства перестановок с трудным битом.
Схемы шифрования с открытым ключом одного бита.
Схемы шифрования с открытым ключом сообщения любой длины: многоразовое использование схемы шифрования одного бита и прямая схема на основе трудного бита односторонней перестановки.
Неинтерактивные схемы привязки к биту.
Интерактивные алгоритмы. Интерактивные протоколы привязки к биту.
Протоколы подбрасывания монетки.
Использование протоколов подбрасывания монетки для игры в орлянку по телефону.
Протоколы идентификации с закрытым ключом: определение и построение протокола на основе ПСФ.
Неразглашение информации. Теорема о последовательном повторении неразглашающего протокола.
Лемма о достаточности устойчивости относительно атаки на протокол идентификации без подслушивания и неразглашения информации.
Протокол индентификации с открытым ключом на основе функции Рабина.
Семейства хэш-функций: УСОХ и СТОК. Построение СТОК, исходя из гипотезы о сильной необратимости функции Рабина.
Одноразовые схемы цифровой подписи: одного бита, сообщения фиксированной длины и сообщения произвольной длины.
Построение многоразовой схемы цифровой подписи на основе одноразовой схемы подписи сообщений произвольной длины и семейства ПСФ.