Abstract:
We consider the operation of the repetition-free product of Boolean functions and the operation generated by it of raising a Boolean function to a power. The powers of a Boolean function were considered by B. A. Subbotovskii (first in 1963) and the author in the solution of the problem of the comparison of Boolean bases. In the present paper we give a criterion that allows us to establish whether a sequence of powers of a function $f$ can be realized by formulas in a basis $B$ with linear or nonlinear complexity.