On the complexity of multivalued logic functions over some infinite basis

V. V. Kochergin ; A. V. Mikhailovich

Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 1, pp. 42-74.

Résumé

Under study is the complexity of the realization of $k$-valued logic functions $(k\ge 3)$ by logic circuits in the infinite basis consisting of the Post negation (i.e., the function $(x+1)modk$) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. For an arbitrary function $f$, we find the lower and upper bounds of complexity which differ from one another at most by $1$ and have the form $3{\log }_3(d(f)+1)+O(1)$, where $d(f)$ is the maximal number of the decrease of the value of $f$ taken over all increasing chains of tuples of values of the variables. We find the exact value of the corresponding Shannon function which characterizes the complexity of the most complex function of a given number of variables. Illustr. 4, bibliogr. 24.

Détail

Mots-clés : multivalued logic functions, logic circuit, infinite basis, inversion complexity.

Bibliographie

[1] N. A. Karpova, “Some properties of Shannon functions”, Math. Notes, 8:5 (1970), 843–849 | DOI | MR | Zbl

[2] O. M. Kasim-Zade, “Complexity of circuits in an infinite basis”, Vestn. Mosk. Univ. Ser. 1, 1994, no. 6, 40–44 (Russian) | MR

[3] O. M. Kasim-Zade, “Orders of growth of Shannon functions for circuit complexity over infinite bases”, Mosc. Univ. Math. Bull., 68:3 (2013), 170–172 | DOI | MR

[4] V. V. Kochergin, “Theory of rectifier circuits (the current state)”, Discrete Mathematics and Its Applications, 7, Izd. IPM RAN, Moscow, 2013, 23–40, (accessed Nov. 16, 2017) Russian Available at http://www.keldysh.ru/dmschool/datastore/media/dmsc9_lect7.pdf

[5] V. V. Kochergin, A. V. Mikhailovich, “On the complexity of circuits in bases containing monotone elements with zero weights”, Prikl. Diskretn. Mat., 2015, no. 4, 24–31 (Russian) | DOI

[6] V. V. Kochergin, A. V. Mikhailovich, “The minimum number of negations in circuits for systems of multi-valued functions”, Discrete Math. Appl., 27:5 (2017), 295–302 | DOI | DOI | MR

[7] O. B. Lupanov, “The synthesis of circuits from threshold elements”, Problems of Cybernetics, 26, Nauka, Moscow, 1973, 109–140 (Russian)

[8] O. B. Lupanov, Asymptotic Estimations of Complexity of Control Systems, Izd. Mosk. Univ., Moscow, 1984 (Russian)

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

[10] A. A. Markov, “On the inversion complexity of systems of Boolean functions”, Sov. Math. Dokl., 4 (1963), 694–696 | MR | Zbl

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

[12] E. I. Nechiporuk, “On a synthesis of schemes of threshold elements”, Problems of Cybernetics, 11, Nauka, Moscow, 1964, 49–62 (Russian) | MR

[13] O. V. Podolskaya, “Circuit complexity of symmetric Boolean functions in an antichain basis”, Discrete Math. Appl., 26:1 (2016), 31–39 | DOI | DOI | MR

[14] J. E. Savage, The Complexity of Computing, Wiley, New York, 1976 | MR

[15] Blais E., Canonne C. L., Oliveira I. C., Servedio R. A., Tan L.-Y., Learning circuits with few negations, Electron. Colloq. Comput. Complex., Rep. No. 144, Available at , 2014, (accessed Nov. 16, 2017) http://eccc.weizmann.ac.il/report/2014/144/download

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

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

[18] Fischer M. J., “The complexity of negation-limited networks – A brief survey”, Automata theory and formal languages, Lect. Notes Comput. Sci., 33, Springer-Verl., Berlin, 1975, 71–82 | DOI | MR

[19] Jukna S., Boolean function complexity: Advances and frontiers, Algorithms Comb., 27, Springer-Verl., Heidelberg, 2012 | MR

[20] Kochergin V. V., Mikhailovich A. V., Some extensions of the inversion complexity of Boolean functions, Cornell Univ. Libr. e-Print Archive, 2015, arXiv: 1506.04485

[21] Kochergin V. V., Mikhailovich A. V., Inversion complexity of functions of multi-valued logic, Cornell Univ. Libr. e-Print Archive, 2015, arXiv: 1510.05942

[22] Morizumi H., A note on the inversion complexity of Boolean functions in Boolean formulas, Cornell Univ. Libr. e-Print Archive, 2008, arXiv: 0811.0699

[23] Pippenger N., “The mimimum number of edges in graphs with prescribed paths”, Math. Syst. Theory, 12:4 (1979), 325–346 | MR

[24] Sung S., Tanaka K., “Limiting negations in bounded-depth circuits: An extension of Markovs theorem”, Algorithms and computation, Lect. Notes Comput. Sci., 2906, Springer-Verl., Heidelberg, 2003, 108–116 | DOI | MR