Bounds of Non-Monotone Complexity for the Multi-Valued Logic Functions
V. V. Kochergin, A. V. Mikhailovich · Učenye zapiski Kazanskogo gosudarstvennogo universiteta. Seriâ Fiziko-matematičeskie nauki/Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki · 2020
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.