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

Article collection "Mathematical Problems of Cybernetics" №15, Moscow, 2006
Authors: Krasulina E.G.
On the complexity of implementing the system of all symmetric functions in the class of switch and valve circuits
Abstract:
The present article considers the problem of implementing all symmetric functions in the class of switch and valve circuits. We construct an asymptotically minimal switch and valve circuit that implements all the symmetric functions. We prove that this implementation of all symmetric functions of n variables by a switch and valve circuit requires asymptotically 7 ·2n-1 elements.
Keywords:
symmetric functions, switch and valve circuit, complexity theory
Publication language: russian,  pages: 18 (p. 165-182)
Russian source text:
Export link to publication in format:   RIS    BibTex