Article collection "Mathematical Problems of Cybernetics" №15, Moscow, 2006
On the complexity of implementing the system of all symmetric functions in the class of switch and valve circuits
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.
symmetric functions, switch and valve circuit, complexity theory