Complexity and Structure of Near-Minimal Contact Circuits
for Elementary Symmetric Functions
E. A. Popov
Department of Mathematical Cybernetics, Faculty of Computational Mathematics and Cybernetics,
Moscow State University, Moscow, 119991 Russia
e-mail: evgeny.a.popov@gmail.com
Received October 31, 2007
Abstract—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 estab-
lished and the estimates of the complexity of the obtained circuits, which are accurate to within an addi-
tive 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(
) = (2w + 1)n –
Bw, where Bw is a nonnegative constant.
DOI:10.3103/S0278641908030072
Pleiades Publishing home page | journal home page | top
If you have any problems with this server, contact webmaster.