Asymptotics of growth for non-monotone complexity of multi-valued logic function systems

V. V. Kochergin ; A. V. Mikhailovich

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 14 (2017), pp. 1100-1107.

Résumé

The problem of the complexity of multi-valued logic functions realization by circuits in a special basis is investigated. This kind of basis consists of elements of two types. The first type of elements are monotone functions with zero weight. The second type of elements are non-monotone elements with unit weight. The non-empty set of elements of this type is finite. In the paper the minimum number of non-monotone elements for an arbitrary multi-valued logic function system $F$ is established. It equals $\lceil\log_{u}(d(F)+1)\rceil - O(1)$. Here $d(F)$ is the maximum number of the value decrease over all increasing chains of tuples of variable values for at least one function from system $F$; $u$ is the maximum (over all non-monotone basis functions and all increasing chains of tuples of variable values) length of subsequence such that the values of the function decrease over these subsequences.

Détail

Keywords: combinational machine (logic circuits), circuits complexity, bases with zero weight elements, $k$-valued logic functions, inversion complexity, Markov's theorem, Shannon function.

Bibliographie

[1] J. of ACM, 5:4 (1958), 331–334 | DOI | MR | Zbl | Zbl

[2] Soviet Math. Doklady, 4 (1963), 694–696 | MR | Zbl

[3] V. V. Kochergin, A. V. Mikhailovich, Inversion complexity of functions of multi-valued logic, Cornell University Library, 2015, arXiv: 1510.05942

[4] Discrete Math. Appl., 27:5 (2017), 295–302 | DOI | DOI | MR

[5] O. B. Lupanov, Asymptotic Estimations of Complexity of Control Systems, Mosc. State Univ. Press, M., 1984 (in Russian)

[6] J. E. Savage, The complexity of computing, Wiley, New York, 1976 | MR | Zbl

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

[8] E. I. Nechiporuk, “On the complexity of circuits in some bases containing nontrivial elements with zero weights”, Problemy Kibernetiki, 8 (1962), 123–160 (in Russian) | MR | Zbl

[9] M. J. Fischer, “The complexity of negation-limited networks — a brief survey”, Springer Lect. Notes in Comput. Sci., 33, 1975, 71–82 | DOI | MR | Zbl

[10] M. J. Fischer, Lectures on network complexity, Technical Report 1104, CS Department, Yale University, 1974; 1996

[11] K. Tanaka, T. Nishino, “On the complexity of negation-limited Boolean networks”, Proceedings of the 26th annual ACM symposium on theory of computing, STOC '94, 1994, 38–47 | Zbl

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

[13] S. Sung, K. Tanaka, “Limiting negations in bounded-depth circuits: an extension of Markov's theorem”, Lect. Notes in Comput. Sci., 2906, 2003, 108–116 | DOI | MR | Zbl

[14] H. Morizumi, A note on the inversion complexity of Boolean functions in Boolean formulas, Cornell University Library, 2008, arXiv: 0811.0699

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

[16] E. Blais, C. L. Canonne, I. C. Oliveira, R. A. Servedio, L.-Y. Tan, Electronic Colloquium on Computational Complexity, 2014, Report No 144

[17] S. Guo, T. Malkin, I. C. Oliveira, A. Rosen, “The power of negations in cryptography”, Lect. Notes in Comput. Sci., 9014, 2015, 36–65 | DOI | MR | Zbl

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

[19] V. V. Kochergin, A. V. Mikhailovich, “On the complexity of circuits in bases containing monotone elements with zero weights”, Prikladnaya Diskretnaya Matematika, 30:4 (2015), 25–32 (in Russian) | DOI