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