Geodesic
Relations between energy complexity measures of Boolean networks and positive sensitivity of Boolean functions
Diskretnaya Matematika, Tome 35 (2023) no. 1, pp. 71-81

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2023_35_1_a4,
     author = {M. A. Mestetskiy and M. S. Shupletsov},
     title = {Relations between energy complexity measures of {Boolean} networks and positive sensitivity of {Boolean} functions},
     journal = {Diskretnaya Matematika},
     pages = {71--81},
     publisher = {mathdoc},
     volume = {35},
     number = {1},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2023_35_1_a4/}
}
TY  - JOUR
AU  - M. A. Mestetskiy
AU  - M. S. Shupletsov
TI  - Relations between energy complexity measures of Boolean networks and positive sensitivity of Boolean functions
JO  - Diskretnaya Matematika
PY  - 2023
SP  - 71
EP  - 81
VL  - 35
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2023_35_1_a4/
LA  - ru
ID  - DM_2023_35_1_a4
ER  - 
%0 Journal Article
%A M. A. Mestetskiy
%A M. S. Shupletsov
%T Relations between energy complexity measures of Boolean networks and positive sensitivity of Boolean functions
%J Diskretnaya Matematika
%D 2023
%P 71-81
%V 35
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2023_35_1_a4/
%G ru
%F DM_2023_35_1_a4
M. A. Mestetskiy; M. S. Shupletsov. Relations between energy complexity measures of Boolean networks and positive sensitivity of Boolean functions. Diskretnaya Matematika, Tome 35 (2023) no. 1, pp. 71-81. http://geodesic.mathdoc.fr/item/DM_2023_35_1_a4/