Laboratory of Mathematical Logic at PDMI

Пятница, 3 марта, комната 106. Начало в 17:30.

Докладчик: А. Кожевников.

Тема: Нижние экспоненциальные оценки на размер статических полуалгебраических доказательств Ловаса-Шрайвера для Цейтинских формул.

Abstract

Продолжение доклада от 17 февраля. В этой части будет передоказана нижняя линейная оценка на булеву степень вывода в Positivestellensatz (изначально доказанная Д. Ю. Григорьевым в 2001 году для степени вывода) и приведены сведения, позволяющие расширить эту нижнюю оценку на булеву степень вывода в static LS.