Laboratory of Mathematical Logic at PDMI

Вторник, 17 октября, комната 106. Начало в 12:00.

вторник, 17 октября 2000 г., 12:00, к.106
состоится два доклада:
1. Докладчик: Э.Гирш
АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ ПРОПОЗИЦИОНАЛЬНЫХ ДОКАЗАТЕЛЬСТВ, ПОЛИНОМИАЛЬНО СИМУЛИРУЮЩИЕ СИСТЕМЫ ФРЕГЕ
В последние годы в области пропозициональных доказательств популярны были алгебраические системы: Nullstellensatz, polynomial calculus, и другие. Для каждой их них в том или ином виде известны экспоненциальные нижние оценки (насколько они "честные", будет обсуждаться в докладе).
Для систем Фреге экспоненциальных нижних оценок не известно. в докладе будет предложен вариант polynomial calculus, который полиномиально симулирует системы Фреге. Отличие от обычного polynomial calculus состоит в том, что полиномы представляются не как суммы мономов, а как алгебраические выражения со скобками, При этом в список правил вывода добавляются аксиомы кольца.
2. Докладчик: Д.В.Карпов
О ВЫДЕЛЕНИИ K НЕ ПЕРЕСЕКАЮЩИХСЯ ПО РЕБРАМ ОСТОВНЫХ ДЕРЕВЬЕВ В 2K-РЕБЕРНО СВЯЗНОМ ГРАФЕ
Будет доказано, что во всяком 2k-реберно связном графе можно выделить k остовных деревьев, никакие два из которых не имеют общих ребер и описана конструкция такого построения.