RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2014 Volume 26, Issue 4, Pages 100–109 (Mi dm1308)

This article is cited 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.

UDC: 519.713

Received: 23.05.2014

DOI: 10.4213/dm1308


 English version:
Discrete Mathematics and Applications, 2015, 25:2, 101–108

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025