×

zbMATH — the first resource for mathematics

Super-quadratic lower bounds on the size of formulas in some bases. (Russian) Zbl 0956.68065
Lower bounds of the form \(n^{2+C}\), where \(C>0\), are obtained for Andreev’s function for formulas over generalized monotone bases.

MSC:
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDF BibTeX XML Cite