Relations between energy complexity measures of Boolean networks and positive sensitivity of Boolean functions

Abstract We study relationships between lower estimates for the energy complexity E ( Σ ), the switching complexity S ( Σ ) of a normalized Boolean network Σ , and the positive sensitivity ps( f ) of the Boolean function f implemented by this circuit. The lower estimate <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mtable columnalign="center" rowspacing="4pt" columnspacing="1em"> <m:mtr> <m:mtd> <m:mstyle displaystyle="true"> <m:mi>E</m:mi> <m:mo stretchy="false">(</m:mo> <m:mrow class="MJX-TeXAtom-ORD"> <m:mi class="MJX-tex-mathit" mathvariant="italic">Σ</m:mi> </m:mrow> <m:mo stretchy="false">)</m:mo> <m:mo>⩾</m:mo> <m:mo fence="false" stretchy="false">⌊</m:mo> <m:mfrac> <m:mrow> <m:mtext>ps</m:mtext> <m:mo stretchy="false">(</m:mo> <m:mi>f</m:mi> <m:mo stretchy="false">)</m:mo> <m:mo>−</m:mo> <m:mn>1</m:mn> </m:mrow> <m:mi>m</m:mi> </m:mfrac> <m:mo fence="false" stretchy="false">⌋</m:mo> </m:mstyle> </m:mtd> </m:mtr> </m:mtable> </m:math> $\begin{array}{} \displaystyle E({\it\Sigma})\geqslant \lfloor\frac{\text{ps}(f)-1}{m}\rfloor \end{array}$ is proved for a sufficiently wide class of bases consisting of monotone Boolean functions of at most m variables, the negation gate, and the Boolean constants 0 and 1. For the switching complexity of circuits, we construct a counterexample which shows that, for the standard basis of elements of the disjunction, conjunction, and negation, there do not exist a linear (with respect to ps( f )) lower estimate for the switching complexity.