Multiplicative complexity of some Boolean functions

S. N. Selezneva

Diskretnaya Matematika, Tome 26 (2014) no. 4, pp. 100-109

Résumé

The multiplicative (or conjunctive) complexity of a Boolean function $f(x_1, \dots, x_n)$ (respectively, of a system of Boolean functions $F = \{f_1, \dots, f_m\}$) is the smallest number of AND gates in circuits in the basis $\{x\ y, x \oplus y, 1\}$ implementing the function $f$ (respectively, all the functions of system $F$). The multiplicative complexity of a function $f$ (of a system of functions $F$) will be denoted by $\mu(f)$ (respectively, $\mu(F)$). It will be shown that $\mu(f) = n-1$ if a function $f(x_1, \dots, x_n)$ is representable as $x_1x_2\dots x_n \oplus q(x_1, \dots, x_n)$, where $q$ is a function of degree two ($n \ge 3$). Moreover, we show that $\mu(f) \le n-1$ if a function $f(x_1, \dots, x_n)$ is representable as a XOR sum of two multiaffine functions. Furthermore, $\mu(F) = n-1$ if $F = \{x_1x_2\dots x_n, f(x_1, \dots, x_n)\}$, where $f$ is a function of degree two or a multiaffine function.

Détail

Keywords: Boolean function, circuit, complexity, multiplicative (conjunctive) complexity, the upper bound.