On the complexity of realizing the powers of a Boolean \((n,n)\)-function (Q1345680)

The studied problem of complexity is presented for circuits with functional elements in the basis \(\&\), \(\vee\), \(-\), the lengths of all chains of the circuits from input to output being equal. The complexity of a circuit \(S\) is the number \(L(S)\) of its gates and its depth \(T(S)\) is the total length of the chains from input to output. The basic result proved gives the complexity of the realization of the powers of the studied Boolean function and upper bounds for \(L(S)\) and \(T(S)\).