Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Пятница, 18 октября 2019, 16:20–17:55
Где: НГУ, ауд. 4117

Описание

Теорема Бен-Сассона и Вигдерсона о связи ширины и размера древовидного и обычного резолюционного доказательства.

Нижняя оценка для графового принципа Дирихле. Следствие для обычного принципа Дирихле.

Видео

Материалы

Текущая версия конспекта тут: https://logic.pdmi.ras.ru/~dmitrits/nsu/pc.pdf