Relations between energy complexity measures of Boolean networks and positive sensitivity of Boolean functions
M. A. Mestetskiy,
M. S. Shupletsov Lomonosov Moscow State University
Abstract:
We study relationships between lower estimates for the energy complexity
$E(\Sigma)$, the switching complexity
$S(\Sigma)$ of a normalized Boolean network
$\Sigma$, and the positive sensitivity
$\operatorname{ps}(f)$ of the Boolean function
$f$ implemented by this circuit. The lower estimate $E(\Sigma)\geqslant \lfloor\frac{\operatorname{ps}(f)-1}{m}\rfloor$ 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
$\operatorname{ps}(f)$) lower estimate for the switching complexity.
Keywords:
Boolean network, energy complexity, switching complexity, positive sensitivity.
UDC:
519.714.4 Received: 18.11.2022
DOI:
10.4213/dm1750