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