On the complexity of circuits in bases containing monotone elements with zero weights

V. V. Kochergin ; A. V. Mikhailovich

Prikladnaâ diskretnaâ matematika, no. 4 (2015), pp. 24-31

Résumé

Complexity of Boolean functions and Boolean function systems realization in a base consisting of all monotone functions and a finite number of non-monotone functions is researched. The weight of any monotone function in the base is supposed to be 0, the weight of non-monotone function in it is positive. A. A. Markov studied special case of this base, where the non-monotone part consisted of the negation function. He showed that the minimum number of negation elements which are needed to realize an arbitrary function $f$ equals $\lceil\log_2(d(f)+1)\rceil$. Here $d(f)$ is the maximum number of value changes from 1 to 0 over all increasing chains of arguments tuples. The aim of this paper is to prove that the complexity of a Boolean function $f$ realization equals $\rho\lceil\log_2(d(f)+1)\rceil-\mathrm O(1)$, where $\rho$ is the minimum weight of non-monotone elements in the base. Similar generalization of the classical Markov's result concerning the realization of Boolean function systems is obtained too.

Détail

Keywords: Boolean circuits, logic circuits, bases with zero weight elements, Boolean function complexity, circuit complexity, inversion complexity, Markov's theorem.