Город: Санкт-Петербург Казань Язык: Русский English

Избранные главы схемной сложности
Санкт-Петербург / осень 2017, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

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

Дата и время Название Место Материалы
26 ноября
11:15–12:45
Лекция 1, лекция ПОМИ РАН Нет
26 ноября
13:00–14:30
Лекция 2, лекция ПОМИ РАН Нет
26 ноября
15:30–17:00
Лекция 3, лекция ПОМИ РАН Нет