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
Voir la notice du chapitre de livre provenant de la source Math-Net.Ru
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 $012\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},
publisher = {mathdoc},
volume = {162},
number = {3},
year = {2020},
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 PB - mathdoc 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 %I mathdoc %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/