Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: multiplicative complexity

Sortuj według:

Ogranicz wyniki do:

On the Multiplicative Complexity of Boolean Functions

Selezneva S. N.

Fundamenta Informaticae

2016

Vol. 145, nr 3

399--404

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) ≤ (v2 + o(1))2n/2, if n is odd. These evaluations improve estimations from [1].