Нижние оценки монотонной сложности логического перманента

Логическим перманентом $f_m$ булевой матрицы $m\times m$ называется монотонная булева функция $\bigvee_{\sigma\in S_m}\&_{i=1}^mx_{i\sigma(i)}$. Монотонной сложностью $L_f^+$ монотонной булевой функции $f$ называется наименьшее число функциональных элементов И, ИЛИ, необходимое для ее реализации в виде функциональной схемы. Доказана нижняя оценка $L_{f_m}^+\ge m^{(C\log m)}$ ($C>0$). Библиогр. 7 назв.