A simplified proof of a lower complexity estimate
V. M. Khrapchenko · Discrete Mathematics and Applications · 2013
- The proof of a well-known inequality which may be used to derive quadratic lower bounds for the complexity of Π-circuits (or, the same, formulae over the basis {&,V-}) for many Boolean functions is significantly simplified. This work was financially supported by the Program of Fundamental Research “Algebraic and Combinatorial Methods of Mathematical Cybernetics” of the Mathematical Sciences Department of the Russian Academy of Sciences (project “Synthesis and Complexity of Control Systems”).