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