Миникурс по сложности пропозициональных доказательств. Ширина и размер резолюционных доказательств

Докладчик: 
Ицыксон Д.М. (ПОМИ РАН)
Дата: 
Friday, November 11, 2016 - 17:30
Место: 
ПОМИ, ауд. 203
Аннотация: 

Миникурс предназначен для студентов, аспирантов и всех интересующихся сложностью пропозициональных доказательств.
В первой лекции будет рассказано о резолюционной системе доказательств. В частности, мы изучим теорему Бен-Сассона и Вигдерсона о связи ширины и размера резолюционных доказательств. В качестве следствия будет приведены доказательства экспоненциальных нижних оценок на размер доказательства цейтинских формул и принципа Дирихле.