Laboratory of Mathematical Logic at PDMI

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

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

Тема: Нижняя оценка $7n/3$ на схемную сложность.

Abstract

Известно, что схемная сложность почти всех булевых функций
экспоненциальна. В то же время наилучшей доказанной нижней оценкой на
схемную сложность до сих пор является оценка $3n$, доказанная в 1984-м
году Н. Блюмом (здесь $n$~--- количество переменных). В докладе будет
рассказано о методе доказательства таких оценок~--- методе элиминации
гейтов. Также будет приведено простое доказательство нижней оценки
7n/3 и сформулировано несколько открытых вопросов.