Article collection "Mathematical Problems of Cybernetics" №1, Moscow, 1988
Authors:Krasulina E.G.
On the complexity of implementing algebra of logic monotone symmetric functions by switching circuits
Abstract:
We consider the problem of implementing algebra of logic monotone symmetric functions in the class of switching circuits. We obtain a new estimate for the implementation of an arbitrary monotone symmetric function by switching circuits, namely that the complexity of any monotone symmetric function is of order no greater than n (ln n)4 / (ln ln n)2.
Keywords:
algebra of logic, symmetric functions, switching circuits, complexity theory
