Пятница 22.05. Артур Рязанов (ПОМИ РАН): "Применение критерия Юкны для нижних оценок в системе доказательств Cutting Planes"

Пятница 22.05. Артур Рязанов (ПОМИ РАН): "Применение критерия Юкны для нижних оценок в системе доказательств Cutting Planes"

Date:

Friday, May 22, 2020 - 18:10

Abstract:

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

Ссылка на конференцию Zoom будет отправлена на рассылку семинара за несколько часов до доклада.