# 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)
##### Keywords:
complexity; Boolean function; lower bound; basis; formula