Избранные главы схемной сложности

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

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