Дневник лекций (осень 2013 года, весна 2014 года)
5 сентября
Равнодоступные адресные машины, меры сложности: количество операций,
длина машинного слова, количество использованных регистров.
Полиномиальные РАМ (по всем трем мерам сложности).
Одноленточные и многоленточные машины Тьюринга. Время работы и память
как меры сложности. Оценка количества шагов для копирования слова.
Оценка сложности выполнения арифметических операций на
машинах Тьюринга.
12 сентября
Моделирование машин Тьюринга на РАМ.
Моделирование многолентночных машин Тьюринга на одноленточных.
Моделирование РАМ на многоленточных машинах Тьюринга.
19 сентября
Класс NP. Примеры.
Определение сводимости по Карпу.
NP трудные и полные задачи.
Теорема Кука—Левина
об NP полноте задачи выолнимости схем из функциональных элементов.
NP полнота задачи 3-CNF.
26 сентября
Схемы из функциональных элементов.
Верхняя оценка O(n2^n) схемной сложности
любой булевой функции.
Нижняя оценка
2^n/3n схемной сложности некоторой булевой функции.
Класс n.u.P и включение класса P в этот класс.
3 октября
Вероятностные алгоритмы.
Полиномальные по времени вероятностные алгоритмы (время ограничено
полиномом от длины входа при любых исходах бросаний).
Определение вычисления с ограниченной ошибкой.
Уменьшение вероятности ошибки с помощью повторения (amplification).
Класс BPP.
Вероятностный полиномиальный алгоритм проверки полиномиального
тождества.
10 октября
Включение BPP в n.u.P.
Сильно односторонние функции (противник — вероятностный
полиномиальный алгоритм). Кандидаты.
Если P=NP, то сильно односторонние функции не существуют.
17 октября
Определение необратимости с противником в виде схемы из функциональных
элементов
Слабо односторонние функции. Преобразование слабо односторонней
функции в сильно одностороннюю.
24 октября
Частичные односторонние функции.
Примеры предположительно односторонних перестановок
31 октября
Вычислительно неотличимые случайные величины.
Определение генератора ПСЧ
7 ноября
Свойства вычислительно неотличимых случайных величин.
Трудный бит для данной перестановки. Общая схема
построения генератора, исходя из односторонней перестановки
и трудного бита.
14 ноября
Лемма о трудном бите. Построение генератора из перестановки
и трудного бита
21 ноября
Теорема Левина-Голдрайха о декодировании кода Адамара
и построении трудного бита для данной односторонней перестановки.
28 ноября
Генераторы, выдающие бесконечно много случайных битов.
Надехность генераторов по Яо и эквивалентность
этого определения обычному.
Преобразование генератора, добавляющего лишь один бит в генератор,
добавляющий сколько угодно битов.
5 декабря
Псевдослучайный функции. Два вида надежности. Построение ПСФ
на основе генератора.
12 декабря
Схемы шифрования с закрытым ключом (симметричные схемы).
Построение одноразовой схемы на основе генератора
Построение многоразовой схемы на основе ПСФ