Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский 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
Лекция, лекция ПОМИ РАН Нет