On the Multiplicative Complexity of Boolean Functions

• Autorzy: Selezneva S. N.

Identyfikatory

DOI

10.3233/FI-2016-1368

• Języki publikacji: EN

Abstrakty

EN

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(x₁, ..., x_n), we can construct a circuit S_f implementing the function f such that µ(S_f) ≤ (3/2 + o(1)) · 2^n/2, if n is even, and µ(S_f) ≤ (v2 + o(1))2^n/2, if n is odd. These evaluations improve estimations from [1].

Słowa kluczowe

EN

Boolean function; circuit; complexity; multiplicative complexity; upper bound

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 3
• Strony: 399--404
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Selezneva S. N.

• Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Moscow, Russia

Bibliografia

• [1] Boyar J, Peralta R, Pochuev D. On the multiplicative complexity of Boolean functions over the basis {∧,⊕, 1}. Theor. Comp. Sci. 2000; 235:43–57.
• [2] Schnorr CP. The multiplicative complexity of Boolean functions. Proc. 1st Internat. Joint Conf of ISSAC 88 and AAECC-6, Rome (1988). Lecture Notes in Computer Science. 1989; 357:45–58. doi:10.1007/3-540-51083-4 47.
• [3] Selezneva SN. The multiplicative complexity of some Boolean functions. Discrete Mathematics and Applications. 2015; 25(2):101–108. doi:10.1515/dma-2015-0010.
• [4] Selezneva SN. On the multiplicative complexity of some Boolean functions. ComputationalMathematics and Mathematical Physics. 2015; 55(4):724–730. doi:10.1134/S0965542515040119.
• [5] Mirwald R, Schnorr CP. The multiplicative complexity of quadratic boolean forms. Theoretical Computer Science. 1992; 102:307–328.
• [6] Selezneva SN. On the multiplicative complexity of quasi-quadratic Boolean functions. Moscow University Computational Mathematics and Cybernetics. 2015; 39(1):18–25. doi:10.3103/S0278641915010069.
• [7] Krasnova TI. On the conjunction complexity of circuits in the Zhegalkin basis for one sequence of Boolean functions. Proc. of XI International Seminar “Discrete Mathematics and its Applications”.Moscow; 2012. p.138–141 (in Russian).
• [8] Boyar J, Peralta R, Pochuev D. Concrete multiplicative complexity of symmetric functions. Technical Report YALEU/DCS/TR1219. Computer Science Department, Yale University; 2001.
• [9] Kojevnikov A, Kulikov AS. Circuit complexity and multiplicative complexity of Boolean functions. Lecture Notes in Computer Science. 2010; 6158:239–245. doi:10.1007/978-3-642-13962-8 27.
• [10] Sergeev IS. A relation between additive and multiplicative complexity of Boolean functions. arXiv:1303. 4177; 2013.
• [11] Nechiporuk EI. On the complexity of schemes in some bases containing nontrivial elements with zero weights. Problemy Kibernetiki. 1962; 8:123–160 (in Russian).
• [12] Boyar J, Peralta R. Short discreet proofs. Lecture Notes in Computer Science. 1996; 1070:131–142. doi:10.1007/3-540-68339-9 12.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).