Laboratory of Mathematical Logic at PDMI

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

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

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

Abstract

В докладе будет доказано, что размер любого доказательства цейтинских формул в статической системе доказательств Ловаса-Шрайвера (LS) экспоненциален. В качестве следствия мы получим нижнюю экспоненциальную оценку на размер древовидного доказательства в LS.