Информация по курсу

Теория сложности вычислений изучает фундаментальные факты о том, какие ресурсы требуются для решения задач того или иного типа (например,  знаменитый открытый вопрос о равенстве классов и — одна из «проблем тысячелетия» — состоит в том, можно ли быстро найти решение всякой задачи, решения к которой можно быстро проверять).
Изучаемые в ней понятия являются базовыми для любых рассуждений о вычислительной сложности — от эффективности работы алгоритмов до надёжности криптосистем.

Эта теория содержит массу открытых вопросов, однако есть в ней и множество красивых теорем и конструкций. Одно из немногих утверждений о равенстве сложностных классов — теорема Шамира для каждой задачи, решаемой с полиномиальной памятью, существует интерактивный протокол (всесильный emph{prover} убеждает полиномиально ограниченного вероятностного emph{verifier}’а). Удивительно на первый взгляд и следующее утверждение (-теорема) решения любой
-задачи можно переписать таким образом, чтобы их можно было проверять, прочитав лишь константное число битов; эта теорема имеет разнообразные применения в теории (ограничения на приближенные алгоритмы) и на практике (blockchains). Этим и другим замечательным фактам и посвящен спецкурс.

Спецкурс предлагается в нечётных семестрах и сопровождается практическими занятиями (решением задач).

Программа курса

Лекторы

Семинаристы