Article collection "Mathematical Problems of Cybernetics" №4, Moscow, 1992
Lower bound of symmetric Boolean function switching circuit complexity
A modification of a method from the author's previous work allows to establish explicitly given nonlinear lower bounds for the complexity of realizing a sequence of symmetric Boolean functions by switching circuits. In particular these bounds are obtained for the majority function, its negation, and the characteristic function of the n-dimensional hypercube middle layer.
switching circuits, complexity, symmetric Boolean function