On the complexity of circuits in bases containing monotone elements with zero weights

V. V. Kochergin ; A. V. Mikhailovich

Prikladnaâ diskretnaâ matematika, no. 4 (2015), pp. 24-31.

Résumé

Complexity of Boolean functions and Boolean function systems realization in a base consisting of all monotone functions and a finite number of non-monotone functions is researched. The weight of any monotone function in the base is supposed to be 0, the weight of non-monotone function in it is positive. A. A. Markov studied special case of this base, where the non-monotone part consisted of the negation function. He showed that the minimum number of negation elements which are needed to realize an arbitrary function $f$ equals $\lceil\log_2(d(f)+1)\rceil$. Here $d(f)$ is the maximum number of value changes from 1 to 0 over all increasing chains of arguments tuples. The aim of this paper is to prove that the complexity of a Boolean function $f$ realization equals $\rho\lceil\log_2(d(f)+1)\rceil-\mathrm O(1)$, where $\rho$ is the minimum weight of non-monotone elements in the base. Similar generalization of the classical Markov's result concerning the realization of Boolean function systems is obtained too.

Détail

Keywords: Boolean circuits, logic circuits, bases with zero weight elements, Boolean function complexity, circuit complexity, inversion complexity, Markov's theorem.

Bibliographie

[1] Lupanov O. B., Asymptotic Estimations of Complexity of Control Systems, MSU Publ., Moscow, 1984 (in Russian)

[2] Savage J. E., The Complexity of Computing, Wiley, N.Y., 1976 | MR | Zbl

[3] Gilbert E. N., “Lattice theoretic properties of frontal switching functions”, J. Math. Phys., 33 (1954), 56–67 | DOI | MR

[4] Markov A. A., “On the inversion complexity of systems of functions”, J. ACM, 5:4 (1958), 331–334 | DOI | MR | Zbl | Zbl

[5] Markov A. A., “On the inversion complexity of systems of Boolean functions.”, Soviet Math. Dokl., 1963, no. 4, 694–696 | Zbl

[6] Nechiporuk E. I., “On the complexity of schemes in some bases containing nontrivial elements with zero weights”, Problemy Kibernetiki, 8, Fizmatgiz Publ., Moscow, 1962, 123–160 (in Russian)

[7] Nechiporuk E. I., “Complexity of schemes in certain bases containing nontrivial elements with zero weights”, Soviet Math. Dokl., 1961, no. 2, 1087–1088 | Zbl

[8] Nechiporuk E. I., “Complexity of superpositions in bases that contain nontrivial linear formulas with zero weights”, Soviet Physics. Dokl., 6:1 (1961), 6–9 | MR | Zbl

[9] Kochergin V. V., Mikhailovich A. V., Some extensions of the inversion complexity of Boolean functions, Cornell University Library, 2015, arXiv: 1506.04485

[10] Morizumi H., “Limiting negations in formulas”, LNCS, 5555, 2009, 701–712 | MR | Zbl

[11] Fischer M. J., “The complexity of negation-limited networks – a brief survey”, LNCS, 33, 1975, 71–82 | MR | Zbl

[12] Tanaka K., Nishino T., Beals R., “Negation-limited circuit complexity of symmetric functions”, Inf. Proc. Lett., 59:5 (1996), 273–279 | DOI | MR | Zbl

[13] Sung S., Tanaka K., “Limiting negations in bounded-depth circuits: an extension of Markovs theorem”, LNCS, 2906, 2003, 108–116 | MR | Zbl

[14] Morizumi H., Suzuki G., “Negation-limited inverters of linear size”, IEICE Trans. Inform. and Systems, E93-D:2 (2011), 257–262

[15] Guo S., Malkin T., Oliveira I. C., Rosen A., “The power of negations in cryptography”, LNCS, 9014, 2015, 36–65 | MR | Zbl

[16] Jukna S., Boolean Function Complexity. Advances and Frontiers, Springer, Berlin–Heidelberg, 2012, 620 pp. | MR | Zbl