Geodesic
Bounds of non-monotone complexity for the multi-valued logic functions
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 311-321 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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<\cdots ) 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. 
@article{UZKU_2020_162_3_a5,
     author = {V. V. Kochergin and A. V. Mikhailovich},
     title = {Bounds of non-monotone complexity for the multi-valued logic functions},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {311--321},
     year = {2020},
     volume = {162},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a5/}
}
TY  - JOUR
AU  - V. V. Kochergin
AU  - A. V. Mikhailovich
TI  - Bounds of non-monotone complexity for the multi-valued logic functions
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2020
SP  - 311
EP  - 321
VL  - 162
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a5/
LA  - ru
ID  - UZKU_2020_162_3_a5
ER  - 
%0 Journal Article
%A V. V. Kochergin
%A A. V. Mikhailovich
%T Bounds of non-monotone complexity for the multi-valued logic functions
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2020
%P 311-321
%V 162
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a5/
%G ru
%F UZKU_2020_162_3_a5
V. V. Kochergin; A. V. Mikhailovich. Bounds of non-monotone complexity for the multi-valued logic functions. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 311-321. http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a5/

[1] Markov A. A., “On the inversion complexity of systems of functions”, J. Assoc. Comput. Mach., 5:4 (1958), 331–334 | DOI | MR | Zbl | Zbl

[2] Markov A. A., “On the inversion complexity of systems of Boolean functions”, Dokl. Akad. Nauk SSSR, 150:3 (1963), 477–479 (In Russian) | Zbl

[3] Lupanov O. B., Asymptotic Estimates of Complexity of Control Systems, Izd. Mosk. Univ., M., 1984, 137 pp. (In Russian)

[4] Savage J. E., The Complexity of Computing, Wiley, N. Y., 1976, 391 pp. | MR | Zbl

[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, 25–32 (In Russian) | DOI

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

[7] Kochergin V. V., Mikhailovich A. V., “On the complexity of multivalued logic functions over some infinite basis”, J. Appl. Ind. Math., 12:1 (2018), 40–58 | DOI | DOI | MR | Zbl

[8] Kochergin V. V., Mikhailovich A. V., “Circuit complexity of $k$-valued logic functions in one infinite basis”, Comput. Math. Model., 30:1 (2019), 13–25 | DOI | MR | Zbl

[9] Kochergin V. V., Mikhailovich A. V., “Asymptotics of growth for non-monotone complexity of multi-valued logic function systems”, Sib. Electron. Math. Rep., 14 (2017), 1100–1107 | DOI | MR | Zbl

[10] Kochergin V. V., Mikhailovich A. V., “Exact value of the nonmonotone complexity of Boolean functions”, Math. Notes, 105:2 (2019), 28–35 | DOI | DOI | MR | Zbl