Home

Семинар 11 января 2007 года

Четверг, 11 января, комната 106. Начало в 17:30.

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

Тема: Нижние оценки для R(CP).

Abstract

На докладе будут рассказаны два улучшения нижней оценки для R(CP) --- резолюционной системы доказательств, оперирующей линейными неравенствами. В частности, для нижней оценки вида $ exp(n^{Omega(1)})/ M^{O(Wlog^2 n) $, где n --- количество переменных, M --- максимальное абсолютное значение коэффициентов в доказательстве, W --- максимальная длина дизъюнкции в доказательстве, которая была доказана Крайчеком в 1998 году, будет показано, как избавиться от M для древовидных R(CP)-доказательств и от W для любых R(CP)-доказательств (и подобных им).