RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2023 Volume 35, Issue 1, Pages 71–81 (Mi dm1750)

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


 English version:
Discrete Mathematics and Applications, 2024, 34:4, 211–219


© Steklov Math. Inst. of RAS, 2024