Complexity and structure of near-minimal contact circuits for elementary symmetric functions
E. A. Popov · Moscow University Computational Mathematics and Cybernetics · 2008
The paper studies the problem of the synthesis of contact circuits for elementary symmetric functions. The structure of minimal contact circuits realizing elementary symmetric functions is established and the estimates of the complexity of the obtained circuits, which are accurate to within an additive constant, are determined. It is proved that, for substantially large n, the complexity of an elementary symmetric function of n variables with the working number w satisfies the relation L(s ) = (2w + 1)n − B w , whereB w is a nonnegative constant.