Лекция 2

Лекция №2 в курсе "Сложность пропозициональных доказательств". Содержание лекции: Однопроходные ветвящиеся программы как система доказательств. Эквивалентность регулярных резолюций и однопроходных ветвящихся программ. Эквивалентность разрешающих деревьев и древовидных резолюций. Ширина резолюционных доказательств. Цейтинские формулы и их свойства, нижняя оценка на ширину через расширительную способность (e(G)). Преподаватель курса: Дмитрий Михайлович Ицыксон - кандидат физико-математических наук, старший научный сотрудник лаборатории математической логики ПОМИ РАН, преподаватель в Академическом университете. Страница лекции на сайте центра: https://compscicenter.ru/courses/Propositional-proof-complexity/nsk/2019-autumn/classes/4894/