Laboratory of Mathematical Logic at PDMI

Пятница, 11 октября, ауд. 106. Начало в 17:00.

Докладчик: Святослав Грязнов (ПОМИ РАН).

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

Abstract

Мы докажем теорему Разборова о нижней оценке на степень доказательства невыполнимости слабого принципа Дирихле (WPHP) в системе доказательств Polynomial calculus. Данный метод был предложен в статье [1]. В статье вводится понятие так называемоего "pigeon dance", который представляет из себя некоторый недетерминированный процесс рассадки кроликов по клеткам. Позднее данная техника была использована в статье [2], в которой Импаляццо, Пудлак и Сгалл доказали более общее утверждение о минимальном количестве используемых мономов в любом PC-доказательстве невыполнимости произвольной формулы.

[1] A. A. Razborov, Lower Bounds for the Polynomial Calculus, Computational Complexity, 7(4), (1998)
[2] R. Impagliazzo, P. Pudlák, and J. Sgall, Lower bounds for the polynomial calculus and the Groebner basis algorithm, Comput. Complexity, 8(2), (1999)