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

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

Date:

Friday, November 11, 2016 - 17:30

Abstract:

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