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

Теория сложности доказательств
Санкт-Петербург / осень 2010, посмотреть все семестры

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

Курс будет посвящён оценкам длины доказательств в первую очередь для утверждений логики высказываний, хотя будут рассмотрены и другие языки. Существование системы, в которой есть доказательство полиномиальной длины для каждой тавтологии, эквивалентно (неправдоподобному) утверждению NP = co-NP. Однако на констатации этого факта вопросы не заканчиваются: даже если такой системы нет, есть ли оптимальная система с самыми короткими доказательствами? Для каких систем мы можем доказать экспоненциальные нижние оценки на длину доказательств? Как длины доказательств связаны со сложностью вычислительных задач? Подобным вопросам и будет посвящён этот курс.

Литература

Дата и время Занятие Место Материалы
09 сентября
19:00–20:35
Введение, Лекция ПОМИ РАН слайды,  видео
23 сентября
18:30–20:55
Системы Фреге, Лекция ПОМИ РАН слайды,  видеофайлы
30 сентября
18:30–20:55
Моделирование секущих плоскостей в системах Фреге, оптимальные системы, Лекция ПОМИ РАН слайды,  видеофайлы
07 октября
18:30–20:55
Непересекающиеся NP-пары, Лекция ПОМИ РАН слайды,  видеофайлы
21 октября
18:30–20:55
Нижняя оценки для CP. Нижняя оценка для цейтинских формул в Res, Лекция ПОМИ РАН слайды,  видеофайлы
28 октября
18:30–20:55
Нижние оценки для принципа Дирихле и корректности метода резолюций, Лекция ПОМИ РАН слайды,  видео
11 ноября
18:30–20:55
Алгебраические и полуалгебраические системы доказательств, Лекция ПОМИ РАН видео
25 ноября
18:30–20:55
Связь сложности древесных доказательств и коммуникационной сложности, Лекция ПОМИ РАН слайды
16 декабря
18:30–20:55
Лекция, Лекция ПОМИ РАН Нет