Laboratory of Mathematical Logic at PDMI

Пятница, 9 марта, комната 106. Начало в 15:30.

Докладчик: А. Куликов.

Тема: Миникурс по сложности формул и схем. Вторая лекция.

Abstract

Будут рассмотрены общие методы доказательства нижних оценок на размер формулы: метод Ходеса и Спекера, метод Фишера, Майера и Патерсона, метод Нечипорука и метод Храпченко. Каждый метод будет сопровожден примером функции, для которой он дает нетривиальную (а в ряде случаев и оптимальную) нижнюю оценку. Никаких предварительных знаний (в частности, ЗНАНИЯ МАТЕРИАЛА ПРОШЛОЙ ЛЕКЦИИ) НЕ ТРЕБУЕТСЯ.