zbMATH — the first resource for mathematics

Lower bounds on the formula sizes for symmetric Boolean functions. (Russian) Zbl 0956.68066
The author obtains lower bounds of the form $$\Omega(n\log n)$$ on the sizes of formulas over an arbitrary finite basis for almost all symmetric Boolean functions.

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