Теория сложности доказательств

Общая информация
ЛекторЭ. А. Гирш
Семестросень 2010
Дата начала09.09.2010
Количество пар12
Язык курсарусский
Вопросы к экзамену
Видеоhttp://lektorium.tv/course/?id=22778
Аннотация

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

Литература

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Введение
(09.09.2010 - 19:00 - 20:35)

На первой лекции будут даны основные определения и рассмотрены примеры систем доказательств. Для понимания курса полезно (но не обязательно!) знание базовых определений теории вычислимости и сложности: машина Тьюринга, (не)вычислимость, класс NP, сводимости между вычислительными задачами: если Вы с ними когда-то познакомились, освежите свои знания перед первой лекцией. http://lektorium.tv/lecture/?id=13039
2. Системы Фреге
(23.09.2010 - 18:30 - 20:55)

http://lektorium.tv/lecture/?id=13063
3. Моделирование секущих плоскостей в системах Фреге, оптимальные системы
(30.09.2010 - 18:30 - 20:55)

http://lektorium.tv/lecture/?id=13086
4. Непересекающиеся NP-пары
(07.10.2010 - 18:30 - 20:55)

http://lektorium.tv/lecture/?id=13082
5. Нижняя оценки для CP. Нижняя оценка для цейтинских формул в Res
(21.10.2010 - 18:30 - 20:55)

http://lektorium.tv/lecture/?id=13096
6. Нижние оценки для принципа Дирихле и корректности метода резолюций
(28.10.2010 - 18:30 - 20:55)

http://lektorium.tv/lecture/?id=13097
7. Алгебраические и полуалгебраические системы доказательств
(11.11.2010 - 18:30 - 20:55)

http://lektorium.tv/lecture/?id=13127
8. Связь сложности древесных доказательств и коммуникационной сложности
(25.11.2010 - 18:30 - 20:55)

http://lektorium.tv/lecture/?id=13126
9. Лекция
(16.12.2010 - 18:30 - 20:55)

Ваша оценка: Пусто Средняя: 3.7 (6 votes)
Share |
Э.А.Гирш со студентами клуба
Эдуард Алексеевич Гирш
	Эдуард Алексеевич Гирш
	Эдуард Алексеевич Гирш