Affiliations: Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Moscow, Russia. [email protected]
Correspondence:
[*]
Address for correspondence: Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Leninskiye Gory, h. 1, b. 52, Moscow, 119991, Russia
Abstract: The multiplicative complexity μ(f) of a Boolean function f is the smallest number of & (of AND gates) in circuits in the basis {x&y, x⊕y, 1} such that each circuit implements the function f. By μ(S) we denote the number of & (of AND gates) in a circuit S in the basis {x&y, x ⊕ y, 1}. We present a method to construct circuits in the basis {x&y, x ⊕ y, 1} for Boolean functions. By this method, for an arbitrary function f(x1, . . . , xn), we can construct a circuit Sf implementing the function f such that μ(Sf) ≤ (3/2 + o(1)) · 2n/2, if n is even, and μ(Sf) ≤ (√2 + o(1))2n/2, if n is odd. These evaluations improve estimations from [1].
