Laboratory of Mathematical Logic at PDMI

Пятница, 21 января, Zoom. Начало в 13:00.

Докладчик: Д. М. Ицыксон (ПОМИ РАН).

Тема: Нижние оценки и вопросы оптимальности для систем доказательств.

Abstract

В докладе будет дан обзор результатов докладчика на следующие темы:

(1) сложность вывода в системах доказательств, основанных на OBDD;
(2) сложность вывода цейтинских формул в зависимости от древесной ширины графа;
(3) нижние оценки на сложность вывода в подсистемах системы Res(+) (резолюция над дизъюнкциями линейных равенств по модулю 2); 
(4) оптимальные эвристические и вероятностные аксепторы.