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

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

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

Материалы:

• Sanjeev Arora and Boaz Barak, Complexity Theory: A Modern Approach.
• Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
• Oded Goldreich, Foundations of Cryptography. Lecture Notes, Weizmann Institute of Science.
• Подобные курсы, читавшиеся лектором ранее (с lecture notes и видеозаписями): Структурная теория сложности (конспекты) Сложностная криптография (конспекты)

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