Home

Пятница, 9 октября, 18:00, к. 106

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

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

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

Abstract

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