City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Selected topics in circuit complexity
Saint Petersburg / autumn 2017, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

Date and time Class|Name Venue|short Materials
05 November
11:15–12:45
Лекция 1, Lecture ПОМИ РАН video
05 November
13:00–14:30
Лекция 2, Lecture ПОМИ РАН video
05 November
15:30–17:00
Лекция 3, Lecture ПОМИ РАН video