On the multiplicative complexity of Boolean functionsстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 28 октября 2016 г.
Аннотация: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].