zbMATH — the first resource for mathematics

On the complexity of the realization of partial Boolean functions by circuits of functional elements. (Russian) Zbl 0719.94028
The Boolean circuits (or circuits of functional elements by the direct translation from Russian) are considered as the computing model for computing partial Boolean functions. Let F(n,m) be the class of all partial Boolean functions of n variables which are defined exactly on m inputs. The question investigated here is how much may the complexities of the hardest function \(f_{n,m}\) in F(n,m) differ if \(f_{n,m}\) is computed on circuits with two different complete bases. An upper bound (as a function depending on n and m) on this difference is established for any two complete bases.

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68R05 Combinatorics in computer science