Article collection "Mathematical Problems of Cybernetics" №19, Moscow, 2019
Authors:Krasulina E.G.
On a lower bound of elementary symmetric functions system implementation by switching circuits
Abstract:
We consider the problem of implementing elementary symmetric algebra of logic functions by switching circuits. In the present article we show that a switching circuit without parasite paths that implements the system of all elementary symmetric functions of n variables contains at least n(n+3)/2 switches.
Keywords:
elementary symmetric functions, switching circuits, complexity theory
