Asymptotics of growth for non-monotone complexity of multi-valued logic function systems

Siberian Electronic Mathematical Reports. 2017. Vol. 14. P. 1100–1107.

Mikhailovich A.V., Kochergin V.V.

The problem of the complexity of multi-valued logic functions realization by circuits in a special basis is investigated. This kind of basis consists of elements of two types. The 􏰌first type of elements are monotone functions with zero weight. The second type of elements are non-monotone elements with unit weight. The non-empty set of elements of this type is fi􏰌nite.

In the paper the minimum number of non-monotone elements for an arbitrary multi-valued logic function system F is established. It equals ⌈logu(d(F)+1)⌉−O(1). Here d(F) is the maximum number of the value decrease over all increasing chains of tuples of variable values for at least one function from system F; u is the maximum (over all non-monotone basis functions and all increasing chains of tuples of variable values) length of subsequence such that the values of the function decrease over these subsequences. 

 

Keywords: функции многозначной логики, multi-valued logic functions, схемная сложность, inversion complexity, Markov's theorem, инверсионная сложность, теорема Маркова, nonmonotone complexity, немонотонная сложность, logic circuits, bases with zero weight elements, схемы из функциональных элементов, базисы с нулевыми весами, circuit complexity, логические схемы, combinational machine