# zbMATH — the first resource for mathematics

On the complexity of degrees of Boolean functions for formulas. (Russian) Zbl 1005.68075
Operations of repetition-free product of Boolean functions and raising to the power of Boolean functions are considered. A criterion is given which makes it possible to determine whether a sequence of degrees of a function $$f$$ can be computed with linear or nonlinear size formulas in an arbitrary basis $$B$$.
##### 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