KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

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
Publication language: russian,  страниц: 10 (p. 113-122)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text: