Volume 25, No 1, 2018, P. 42-74

UDC 519.714
V. V. Kochergin and A. V. Mikhailovich
On the complexity of multivalued logic functions over some infinite basis

Abstract:
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)$ mod $k$) 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.

Keywords: multivalued logic functions, logic circuit, infinite basis, inversion complexity.

DOI: 10.17377/daio.2018.25.587

Vadim V. Kochergin ¹
Anna V. Mikhailovich ²
1. Lomonosov Moscow State University,
1 Leninskie Gory, 119991 Moscow, Russia
2. National Research University “Higher School of Economics”,
20 Myasnitskaya St., 101000 Moscow, Russia
e-mail: vvkoch@yandex.ru, avmikhailovich@gmail.com

Received 4 August 2017
Revised 6 October 2017

References

[1] N. A. Karpova, Some properties of Shannon functions, Mat. Zametki, 8, No. 5, 663–674, 1970 [Russian]. Translated in Math. Notes, 8, No. 5, 843–849, 1970.

[2] O. M. Kasim-Zade, Complexity of circuits in an infinite basis, Vestn. Mosk. Univ., Ser. 1, No. 6, 40–44, 1994 [Russian].

[3] O. M. Kasim-Zade, Orders of growth of Shannon functions for circuit complexity over infinite bases, Vestn. Mosk. Univ., Ser. 1, No. 3, 55–57, 2013 [Russian]. Translated in Mosc. Univ. Math. Bull., 68, No. 3, 170–172, 2013.

[4] V. V. Kochergin, Theory of rectifier circuits (the current state), in Diskretnaya matematika i eyo prilozheniya (Discrete Mathematics and Its Applica?tions), Vol. 7, pp. 23–40, Izd. IPM RAN, Moscow, 2013 [Russian]. Available at http://www.keldysh.ru/dmschool/datastore/media/ dmsc9_lect7.pdf (accessed Nov. 16, 2017).

[5] V. V. Kochergin and A. V. Mikhailovich, On the complexity of circuits in bases containing monotone elements with zero weights, Prikl. Diskretn. Mat., No. 4, 24–31, 2015 [Russian].

[6] V. V. Kochergin and A. V. Mikhailovich, The minimum number of negations in circuits for systems of multi-valued functions, Diskretn. Mat., 28, No. 4, 80–90, 2016 [Russian]. Translated in Discrete Math. Appl., 27, No. 5, 295–302, 2017.

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

[8] O. B. Lupanov, Asimptoticheskie otsenki slozhnosti upravlyayushchikh sistem (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, Dokl. Akad. Nauk SSSR, 116, No. 6, 917–919, 1957 [Russian]. Translated in J. ACM, 5, No. 4, 331–334, 1958.

[10] A. A. Markov, On the inversion complexity of systems of Boolean functions, Dokl. Akad. Nauk SSSR, 150, No. 3, 477–479, 1963 [Russian]. Translated in Sov. Math., Dokl., 4, 694–696, 1963.

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

[12] E. I. Nechiporuk, On a synthesis of schemes of threshold elements, Problemy Kibernetiki (Problems of Cybernetics), Vol. 11, pp. 49–62, Nauka, Moscow, 1964 [Russian].

[13] O. V. Podolskaya, Circuit complexity of symmetric Boolean functions in an antichain basis, Diskretn. Mat., 27, No. 3, 95–107, 2015 [Russian]. Translated in Discrete Math. Appl., 26, No. 1, 31–40, 2016.

[14] J. E. Savage, The Complexity of Computing, Wiley, New York, 1976. Translated under the title Slozhnost’ vychislenii, Faktorial, Moscow, 1998 [Russian].

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

[16] E. N. Gilbert, Lattice theoretic properties of frontal switching functions, J. Math. Phys., 33, No. 1, 57–67, 1954.

[17] S. Guo, T. Malkin, I. C. Oliveira, and A. Rosen, The power of negations in cryptography, in Theory of Cryptography, pp. 36–65, Springer, Heidelberg, 2015 (Lect. Notes Comput. Sci., Vol. 9014).

[18] M. J. Fischer, The complexity of negation-limited networks — A brief survey, in Automata Theory and Formal Languages, pp. 71–82, Springer-Verl., Berlin, 1975 (Lect. Notes Comput. Sci., Vol. 33).

[19] S. Jukna, Boolean Function Complexity: Advances and Frontiers, Springer, Heidelberg, 2012 (Algorithms Comb., Vol. 27).

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

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

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

[23] N. Pippenger, The minimum number of edges in graphs with prescribed paths, Math. Syst. Theory, 12, No. 4, 325–346, 1979.

[24] S. Sung and K. Tanaka, Limiting negations in bounded-depth circuits: An extension of Markovs theorem, Algorithms and Computation, pp. 108–116, Springer, Heidelberg, 2003 (Lect. Notes Comput. Sci., Vol. 2906).