Laboratory of Mathematical Logic at PDMI

Пятница, 22 мая, Zoom. Начало в 18:10.

Докладчик: Артур Рязанов (ПОМИ РАН).

Тема: Применение критерия Юкны для нижних оценок в системе доказательств Cutting Planes.

Abstract

Это продолжение предыдущего доклада. Мы рассмотрим взвешенный критерий Стасиса Юкны для доказательства нижних оценок на монотонную вещественную схемную сложность. Затем мы покажем, как его применить для доказательства экспоненциальной нижней оценки на сложность опровержения бинарного принципа Дирихле в системе доказательств Cutting Planes (результат Павла Пудлака и Павла Грубеша).

Видео доклада: https://www.youtube.com/watch?v=9CepOg7FG8g