Пятница 05.06. Дмитрий Соколов (СПбГУ, ПОМИ): "Нижние оценки на систему AC_0-Frege"
Speaker:
Дмитрий Соколов (СПбГУ, ПОМИ)
Date:
Friday, June 5, 2020 - 16:00
Place:
Zoom
Abstract:
В этом докладе мы обсудим детали доказательства нижней оценки на систему доказательств AC_0-Frege. Нашей основной целью будет разобраться в технических деталях switching леммы для паросочетаний из классической статьи Urquhart, Fu ``Simplified Lower Bounds for Propositional Proofs''.