×

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