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

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

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

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

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

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