×

On formula complexity for products of Boolean functions. (Russian) Zbl 1009.68056

Let \(f(x_1,\dots,x_n)\) and \(g(x_1,\dots,x_m)\) be Boolean functions. A function \[ (f\otimes g)(x_1,\dots,x_{nm})= f\bigl(g(x_1,\dots,x_m),\dots,g(x_{(n-1)m+1},\dots,x_{nm})\bigr) \] is called a repetition-free product of Boolean functions. A criterion is given that makes it possible to check whether a sequence of products of Boolean functions can be computed with linear size formulas in a 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)
PDFBibTeX XMLCite