Improvement of Nonmonotone Complexity Estimates of k-Valued Logic Functions

Mathematical notes. 2023. Vol. 113. No. 5. P. 794–803.

Kochergin V., Mikhailovich A.

The problem of determining the nonmonotone complexity of the implementation ofk-valued logic functions by logic circuits in bases consisting of all monotone (with respect to thestandard order) functions and finitely many nonmonotone functions is investigated. In calculatingthe complexity measure under examination only those elements of the circuit which are assignednonmonotone basis functions are taken into account. The nonmonotone complexity of an arbitraryk-valued logic function is determined with high accuracy, namely, upper and lower bounds whichdiffer by a constant not exceeding 3 log_2 k + 4 are found/

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