The minimum number of negations in circuits for systems of multi-valued functions

V. V. Kochergin ; A. V. Mikhailovich

Diskretnaya Matematika, Tome 28 (2016) no. 4, pp. 80-90.

Résumé

The paper is concerned with the complexity of realization of $k$-valued logic functions by logic circuits over an infinite complete bases containing all monotone functions; the weight of monotone functions (the cost of use) is assumed to be $0$. The complexity problem of realizations of Boolean functions over a basis having negation as the only nonmonotone element was completely solved by A. A. Markov. In 1957 he showed that the minimum number of NOT gates sufficient for realization of any Boolean function $f$ (the inversion complexity of the function $f$) is $\lceil\log_2(d(f)+1)\rceil$. Here $d(f)$ is the maximum number of the changes of the function $f$ from larger to smaller values over all increasing chains of tuples of variables values. In the present paper Markov's result is extended to the case of realization of $k$-valued logic functions. We show that the minimum number of Post negations (that is, functions of the form $x+1\pmod{k}$) that is sufficient to realize an arbitrary function of $k$-valued logic is $\lceil\log_2(d(f)+1)\rceil$ and the minimum number of Łukasiewicz negation (that is, functions of the form $k-1-x$) that is sufficient to realize an arbitrary $k$-valued logic function is $\lceil\log_k(d(f)+1)\rceil$. In addition, another classical Markov's result on the inversion complexity of systems of Boolean functions is extended to the setting of systems of functions of $k$-valued logic.

Détail

Keywords: multi-valued logic functions, logic circuits, circuit complexity, nonmonotone complexity, inversion complexity, Markov's theorem.

Bibliographie

[1] Gilbert E. N., “Teoretiko-strukturnye svoistva zamykayuschikh pereklyuchatelnykh funktsii”, Kiberneticheskii sbornik, 1, Izd-vo inostrannoi literatury, M., 1960, 175–188; E. N. Gilbert, “Lattice theoretic properties of frontal switching functions”, J. Math. Phys, 33 (1954), 56–67 | DOI | MR

[2] Kochergin V. V., Mikhailovich A. V., “O slozhnosti skhem v bazisakh, soderzhaschikh monotonnye elementy s nulevymi vesami”, Prikladnaya diskretnaya matematika, 2015, no. 4(30), 24–31

[3] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo Moskovskogo universiteta, M., 1984

[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. Doklady, 4 (1963), 694–696 | Zbl

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

[7] Sevidzh D. E., Slozhnost vychislenii, Faktorial, M., 1998; Savage J. E., The complexity of computing, Wiley, New York, 1976 | MR | Zbl

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

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

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

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

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

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

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

[15] Morizumi H., “Limiting negations in formulas”, Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, v. I, Lect. Notes Comput. Sci., 5555, 2009, 701–712 | DOI | MR | Zbl

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

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

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