Санкт-Петербург, 199178, Россия, 14-ая линия Васильевского острова, дом 29
(812) 363-68-71, (812) 363-68-72
ru

Теория сложности вычислений

2019 – 2020, V, VII семестр

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

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

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

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


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


Лекции