Bounds of non-monotone complexity for the multi-valued logic functions

V.V. Kochergin^a,b∗ , A.V. Mikhailovich^b∗∗

^aLomonosov Moscow State University, Moscow, 119991 Russia

^bNational Research University – Higher School of Economics, Moscow, 101000 Russia

E-mail: ^∗vvkoch@yandex.ru, ^∗∗avmikhailovich@gmail.com

Received August 17, 2020

Full text PDF

DOI: 10.26907/2541-7746.2020.3.311-321

For citation: Kochergin V.V., Mikhailovich A.V. Bounds of non-monotone complexity for the multi-valued logic functions. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 311–321. doi: 10.26907/2541-7746.2020.3.311-321. (In Russian)

Abstract

The non-monotone complexity of realization of k-valued logic functions by circuits in a special basis was investigated. The basis consists of elements of two types: the first type comprises all monotone functions (with respect to the order 0 < 1 < 2 <···< k−1 ) with zero weight; the second type includes non-monotone elements with unit weight, the non-empty set of which is finite. The upper and lower bounds of non-monotone complexity (the minimum number of non-monotone elements) for an arbitrary k-valued logic function were established. The difference between the upper and lower bounds does not exceed a universal constant. The difference between the best upper and lower bounds known before is a constant that depends on the basis. The range of values for these constants is infinite.

Keywords: logic circuits, circuit complexity, k-valued logic functions, bases with zero weight elements, inversion complexity, non-monotone complexity

Acknowledgments. This study was supported in part by the Russian Foundation for Basic Research (project no. 18-01-00337).

References

1. Markov A.A. On the inversion complexity of systems of functions. J. Assoc. Comput. Mach., 1958, vol. 5, no. 4, pp. 331–334. doi: 10.1145/320941.320945.
2. Markov A.A. On the inversion complexity of systems of Boolean functions. Dokl. Akad. Nauk SSSR, 1963, vol. 150, no. 3, pp. 477–479. (In Russian)
3. Lupanov O.B. Asimptoticheskie otsenki slozhnosti upravlyayushchikh sistem [Asymptotic Estimates of Complexity of Control Systems]. Moscow, Izd. Mosk. Univ., 1984. 137 p. (In Russian)
4. Savage J.E. The Complexity of Computing. New York, Wiley, 1976. 391 p. (In Russian)
5. Kochergin V.V., Mikhailovich A.V. On the complexity of circuits in bases containing monotone elements with zero weights. Prikl. Diskretn. Mat., 2015, no. 4, pp. 25–32. doi: 10.17223/20710410/30/2. (In Russian)
6. Kochergin V.V., Mikhailovich A.V. The minimum number of negations in circuits for systems of multi-valued functions. Discrete Math. Appl., 2017, vol. 27, no. 5, pp. 295– 302. doi: 10.1515/dma-2017-0030.
7. Kochergin V.V., Mikhailovich A.V. On the complexity of multivalued logic functions over some infinite basis. J. Appl. Ind. Math., 2018, vol. 12, no. 1, pp. 40–58. doi: 10.1134/S1990478918010052.
8. Kochergin V.V., Mikhailovich A.V. Circuit complexity of k-valued logic functions in one infinite basis. Comput. Math. Model., 2019, vol. 30, no. 1, pp. 13–25. doi: 10.1007/s10598-019-09430-5.
9. Kochergin V.V., Mikhailovich A.V. Asymptotics of growth for non-monotone complexity of multi-valued logic function systems. Sib. Electron. Math. Rep., 2017, vol. 14, pp. 1100– 1107. doi: 10.17377/semi.2017.14.093.
10. Kochergin V.V., Mikhailovich A.V. Exact value of the nonmonotone complexity of Boolean functions. Math. Notes, 2019, vol. 105, no. 2, pp. 28–35. doi: 10.1134/S0001434619010048.

The content is available under the license Creative Commons Attribution 4.0 License.