Сложность вычислений и основы криптографии

Санкт-Петербург, весна 2012

Описание

Учёным всегда было присуще стремление разрабатывать эффективные методы решения как можно более широких классов задач. Однако чем более общей является задача, тем менее эффективны алгоритмы для неё. Поэтому важно понимать, какую цену мы платим за усложнение решаемой задачи. Иначе говоря, важно уметь анализировать сложность вычислительных задач. Этим занимается теория сложности алгоритмов, современная быстро развивающаяся область, знание которой совершенно необходимо тем, кто интересуется теоретической информатикой.

Структурная теория сложности изучает классы вычислительных задач и взаимоотношения между ними. Эта область на стыке математики и информатики содержит как великие нерешенные задачи (например, P=?=NP, за решение которой, кстати, объявлен приз в $1,000,000), так и красивые теоремы и понятия (например, интерактивные протоколы). Первая часть курса будет посвящена базовым понятиям, конструкциям, фактам в этой области: вероятностные алгоритмы, вычисления с оракулами, полиномиальная иерархия, булевы схемы, интерактивные протоколы.

Сложность вычислительной задачи препятствует её эффективному решению. Однако зачастую именно это требуется, когда речь идёт о невозможности взлома криптографических протоколов. Вторая часть курса будет посвящена рассказу о криптографических понятиях (односторонних функциях, криптосистемах и т.д.) на языке теории сложности (на котором они, собственно, и определяются).

Материалы:

Условия сдачи курса и вопросы к экзамену.

Преподаватели

Список лекций

Лекция

Недетерминированные машины Тьюринга. Классы P и NP. Оптимальный алгоритм Левина. Сводимости, NP-полнота.

Лекция

NP-полнота задач CIRCUIT-SAT и SAT. Сведение поиска к распознаванию. Существование не NP-полной не полиномиально разрешимой задачи в NP.

Лекция

Оракульные вычисления. Полиномиальная иерархия. Полнота задачи \( QBF_k \). Теоремы о коллапсе. Семейства схем полиномиального размера. Коллапс полиномиальной иерархии как следствие \( NP\subseteq P/poly \). Языки во втором уровне полиномиальной иерархии, не имеющие схем фиксированного полиномиального размера

Лекция

Вычисления с ограничениями по памяти. Схемы полилогарифмической глубины.

Лекция

QBF is PSPACE-complete. Hierarchies DSpace, DTime, NTime.

Лекция

Вероятностные алгоритмы.

Лекция

Интерактивные протоколы.

Лекция

Сложность в среднем. Односторонние функции.

Лекция

Трудный бит. Псевдослучайный генератор.

Лекция

Односторонние функции с секретом, криптосистемы с открытым ключом.

Лекция

Цифровые подписи.