zbMATH — the first resource for mathematics

Complexity of realization of symmetric Boolean functions by switching circuits. (Russian) Zbl 0812.94029
This paper is a valuable contribution to Boolean function complexity theory, especially for the development of lower bound proof techniques. The author investigates the 25-year-old open problem of whether any symmetric Boolean function can be realized with linear complexity by contact schemes (switching circuits). Due to the almost linear \((O(n (\log n)^ 2/ \log\log n)\), \(O(n(\log n)^ 4/ (\log\log n)^ 2))\) upper bounds on the complexity of some subclasses of symmetric Boolean functions established in earlier papers by O. B. Lupanov [Probl. Kibern. 15, 85-99 (1965)] and E. G. Krasulina [Mat. Vopr. Kobern. 1, 140-167 (1988; Zbl 0668.94021)], the hypothesis that any symmetric function has linear complexity has been formulated. Here, it is shown that there exist symmetric Boolean functions which have nonlinear complexity (by contact schemes realization). The method of proof is interesting and is based on nontrivial combinatorial considerations. The paper should be of great interest to anyone dealing with lower bound proofs in complexity theory.

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q25 Analysis of algorithms and problem complexity