Abstract:
A canonical polarized polynomial of a Boolean function $F$ in $n$ variables is a polynomial where one part of the variables of the function $F$ enters the summands only with negation and the second part only without negation. By the complexity of function $F$ in a class of canonical polarized polynomials $l(F)$ we mean the minimum length (number of summands) among all the $2^n$ canonical polarized polynomials of $F$. The Shannon function $L(n)$ for estimating the complexity of functions in $n$ variables in the class of canonical polarized polynomials is defined as $L(n)=\max l(F)$, where the maximum is taken over all functions $F$ in $n$ variables. Here we present the results of investigations of the function $L(n)$.