Пятница, 9 октября, комната 106. Начало в 18:00.
Докладчик: А. С. Куликов.
Тема: Нижняя оценка
на схемную сложность.
Abstract
Известно, что схемная сложность почти всех булевых функций
экспоненциальна. В то же время наилучшей доказанной нижней оценкой на
схемную сложность до сих пор является оценка
![$ 3n $](../../../sites/default/files/tex/f733f5d5349ad9f29c39192e58dd0813eeeb0707/index.png)
, доказанная в 1984-м
году Н. Блюмом (здесь
![$ n $](../../../sites/default/files/tex/31360359740de028d2dd0d2cc8087938c3b61794/index.png)
~--- количество переменных). В докладе будет
рассказано о методе доказательства таких оценок~--- методе элиминации
гейтов. Также будет приведено простое доказательство нижней оценки
7n/3 и сформулировано несколько открытых вопросов.