Geodesic
Multiplicative complexity of some Boolean functions
Diskretnaya Matematika, Tome 26 (2014) no. 4, pp. 100-109
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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, complexity, multiplicative (conjunctive) complexity, the upper bound.
Mots-clés : circuit 
@article{DM_2014_26_4_a9,
     author = {S. N. Selezneva},
     title = {Multiplicative complexity of some {Boolean} functions},
     journal = {Diskretnaya Matematika},
     pages = {100--109},
     year = {2014},
     volume = {26},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2014_26_4_a9/}
}
TY  - JOUR
AU  - S. N. Selezneva
TI  - Multiplicative complexity of some Boolean functions
JO  - Diskretnaya Matematika
PY  - 2014
SP  - 100
EP  - 109
VL  - 26
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2014_26_4_a9/
LA  - ru
ID  - DM_2014_26_4_a9
ER  - 
%0 Journal Article
%A S. N. Selezneva
%T Multiplicative complexity of some Boolean functions
%J Diskretnaya Matematika
%D 2014
%P 100-109
%V 26
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2014_26_4_a9/
%G ru
%F DM_2014_26_4_a9
S. N. Selezneva. Multiplicative complexity of some Boolean functions. Diskretnaya Matematika, Tome 26 (2014) no. 4, pp. 100-109. http://geodesic.mathdoc.fr/item/DM_2014_26_4_a9/

[1] Nechiporuk E.I., “O slozhnosti skhem v nekotorykh bazisakh, soderzhaschikh netrivialnye elementy s nulevymi vesami”, Problemy kibernetiki, 8 (1962), 123–160, Fizmatlit, M.

[2] Boyar J., Peralta R., Pochuev D., “On the multiplicative complexity of Boolean functions over the basis $\{\wedge, \oplus, 1\}$”, Theor. Comput. Sci., 235 (2000), 43–57 | DOI | MR | Zbl

[3] Schnorr C.P., “The multiplicative complexity of Boolean functions”, Proc. of 6th Int. Conf. AAECC-6, Lect. Notes Comput. Sci., 357, Springer, Berlin, 1989, 45–58 | DOI | MR

[4] Mirwald R., Schnorr C.P., “The multiplicative complexity of quadratic Boolean forms”, Theor. Comput. Sci., 102 (1992), 307–328 | DOI | MR | Zbl

[5] Boyar J., Peralta R., Pochuev D., Concrete multiplicative complexity of symmetric functions, Tech. Rep. YALEU/DCS/TR1219. Comput. Sci. Dep. Yale Univ., 2001

[6] Boyar J., Peralta R., “The exact multiplicative complexity of the Hamming weight function”

[7] Krasnova T.I., “O kon'yunktivnoi slozhnosti skhem v bazise Zhegalkina dlya odnoi posledovatelnosti bulevykh funktsii”, Materialy XI Mezhdunar. sem. “Diskretnaya matematika i ee prilozheniya”, Izd-vo mekh-mat. f-ta MGU, M., 2012, 138–141

[8] Kojevnikov A., Kulikov A.S., “Circuit complexity and multiplicative complexity of Boolean functions”, Proc. of 6th Conf. on Computability (CiE 2010), Lect. Notes Comput. Sci., 6158, Springer, Berlin, 2010, 239–245 | DOI | MR | Zbl

[9] Sergeev I.S., “A relation between additive and multiplicative complexity of Boolean functions”, 2013, arXiv: 1303.4177

[10] Yablonskii S.V., Vvedenie v diskretnuyu matematiku, Vysshaya shkola, M., 2001

[11] Kurosh A.G., Kurs vysshei algebry, Nauka, M., 1971 | Zbl

[12] Schaefer T.J., “The complexity of satisfiability problems”, Proc. of the 10th ACM Symp. on Theory of Computing, 1978, 216–226 | MR | Zbl