|
This article is cited in 2 scientific papers (total in 2 papers)
Multiplicative complexity of some Boolean functions
S. N. Selezneva M. V. Lomonosov Moscow State University
Abstract:
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.
Keywords:
Boolean function, circuit, complexity, multiplicative (conjunctive) complexity, the upper bound.
Received: 23.05.2014
Citation:
S. N. Selezneva, “Multiplicative complexity of some Boolean functions”, Diskr. Mat., 26:4 (2014), 100–109; Discrete Math. Appl., 25:2 (2015), 101–108
Linking options:
https://www.mathnet.ru/eng/dm1308https://doi.org/10.4213/dm1308 https://www.mathnet.ru/eng/dm/v26/i4/p100
|
| Statistics & downloads: |
| Abstract page: | 561 | | Full-text PDF : | 239 | | References: | 74 | | First page: | 36 |
|