08.12.2015 Обобщения метода элиминации гейтов для доказательства нижних оценок на схемную сложность (Александр Куликов)

Известно, что случайная булева функция от $n$ переменных требует схем размера $\Theta(2^n/n)$. В то же время наилучшей нижней оценкой для явно заданной булевой функции (то есть функции из $NP$) является оценка $3n−o(n)$, доказанная Блюмом более тридцати лет назад. Эта оценка, как и почти все предыдущие, доказана методом элиминации гейтов. Идея данного метода очень проста: чтобы доказать нижнюю оценку $cn$ на схемную сложность функций из некоторого класса, показывается, что для любой схемы, вычисляющей функцию из этого класса, можно найти подстановку константы входной переменной, удаляющей хотя бы $c$ гейтов; нижняя оценка тогда следует по индукции. В докладе будут рассмотрены возможные способы обобщения данного метода. Мы приведём очень простое доказательство нижней оценки $3n − o(n)$ для аффинных дисперсеров. Это функции, не обращающиеся в константу ни на каком аффинном подпространстве достаточно большой размерности. Эквивалентное определение таково: функция не обращается в константу под любыми линейными подстановками. После этого мы опишем общие идеи получения более сильной нижней оценки для аффинных дисперсеров. Наконец, мы покажем, что существование явно заданных дисперсеров для квадратичных многообразий даёт более сильные оценки.