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

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
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.
elementary symmetric functions, switching circuits, complexity theory
Publication language: russian,  pages: 10 (p. 113-122)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Krasulina Elena Gennad'evna,  ,  Математический институт им. В. А. Стеклова РАН