Laboratory of Mathematical Logic at PDMI

Вторник, 21 марта, комната 412. Начало в 15:00.

Докладчик: В. Жижкун.

ДОКАЗАТЕЛЬСТВА КАК ИГРЫ
доклад на основе статьи p.pudlak "proofs as games" (http://www.math.cas.cz/~pudlak/prfgame.ps)
Предлагается интересный способ получения нижней оценки (экспоненциальной) размера вывода pigeon hole principle методом резолюций. Вывод рассматривается как игра двух игроков: prover'а, который пытается получить противоречие из отрицания доказываемой формулы, и его оппонента, который пытается ему в этом помешать. В таких терминах нижняя оценка соответствует оптимальной стратегии оппонента.