Пятница 11.10. Святослав Грязнов (ПОМИ РАН): "Нижняя оценка на степень вывода слабого принципа Дирихле с использованием метода pigeon dance"
PDMI seminars
Тема: Нижняя оценка на степень вывода слабого принципа Дирихле с использованием метода pigeon dance
Место: ауд. 106
Время: 11.10.2019, 17:00
Докладчик: Святослав Грязнов (ПОМИ РАН)
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)