×

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)
PDF BibTeX XML Cite