Данный курс посвящен нескольким классическим результатам схемной сложности.

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