Exact Value of the Nonmonotone Complexity of Boolean Functions

V. V. Kochergin ; A. V. Mikhailovich

Matematičeskie zametki, Tome 105 (2019) no. 1, pp. 32-41.

Résumé

We study the complexity of the realization of Boolean functions by circuits in infinite complete bases containing all monotone functions with zero weight (cost of use) and finitely many nonmonotone functions with unit weight. The complexity of the realization of Boolean functions in the case where the only nonmonotone element of the basis is negation was completely described by A. A. Markov: the minimum number of negations sufficient for the realization of an arbitrary Boolean function $f$ (the inversion complexity of the function $f$) is equal to $\lceil\log_{2}(d(f)+1)\rceil$, where $d(f)$ is the maximum (over all increasing chains of sets of values of the variables) number of changes of the function value from 1 to 0. In the present paper, this result is generalized to the case of the computation of Boolean functions over an arbitrary basis $B$ of prescribed form. It is shown that the minimum number of nonmonotone functions sufficient for computing an arbitrary Boolean function $f$ is equal to $\lceil\log_{2}(d(f)/D(B)+1)\rceil$, where $D(B)=\max d(\omega)$; the maximum is taken over all nonmonotone functions $\omega$ of the basis $B$.

Détail

Keywords: Boolean (logical) circuits, circuits of functional elements, circuit complexity, inversion complexity, nonmonotone complexity.

Bibliographie

[1] A. A. Markov, “Ob inversionnoi slozhnosti sistem funktsii”, Dokl. AN SSSR, 116:6 (1957), 917–919 | MR | Zbl

[2] O. B. Lupanov, Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo Mosk. un-ta, M., 1984

[3] D. E. Sevidzh, Slozhnost vychislenii, Faktorial, M., 1998 | MR | Zbl

[4] A. A. Markov, “Ob inversionnoi slozhnosti sistemy bulevykh funktsii”, Dokl. AN SSSR, 150:3 (1963), 477–479 | MR | Zbl

[5] E. N. Gilbert, “Teoretiko-strukturnye svoistva zamykayuschikh pereklyuchatelnykh funktsii”, Kiberneticheskii sbornik, Vyp. 1, IL, M., 1960, 175–188

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

[7] M. J. Fischer, “The complexity of negation-limited networks – a brief survey”, Automata Theory and Formal Languages, Lecture Notes in Comput. Sci., 33, Springer-Verlag, Berlin, 1975, 71–82 | MR | Zbl

[8] H. Morizumi, A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas, 2008, arXiv: 0811.0699

[9] S. Jukna, Boolean Function Complexity. Advances and Frontiers, Algorithms Combin., 27, Springer-Verlag, Berlin, 2012 | MR | Zbl

[10] E. Blais, C. L. Canonne, I. C. Oliveira, R. A. Servedio, L.-Y. Tan, “Learning circuits with few negations”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, LIPIcs. Leibniz Int. Proc. Inform., 40, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015, 512–527 | MR

[11] S. Guo, T. Malkin, I. C. Oliveira, A. Rosen, “The power of negations in cryptography”, Theory of Cryptography. Part I, Lecture Notes in Comput. Sci., 9014, Springer-Verlag, Berlin, 2015, 36–65 | MR | Zbl

[12] V. V. Kochergin, A. V. Mikhailovich, Inversion Complexity of Functions of Multi-Valued Logic, 2015, arXiv: 1510.05942

[13] V. V. Kochergin, A. V. Mikhailovich, “O minimalnom chisle otritsanii pri realizatsii sistem funktsii mnogoznachnoi logiki”, Diskret. matem., 28:4 (2016), 80–90 | DOI | MR

[14] V. V. Kochergin, A. V. Mikhailovich, Some Extensions of the Inversion Complexity of Boolean Function, 2015, arXiv: 1506.04485

[15] V. V. Kochergin, A. V. Mikhailovich, “O slozhnosti skhem v bazisakh, soderzhaschikh monotonnye elementy s nulevymi vesami”, PDM, 2015, no. 4 (30), 24–31 | DOI