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
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2023},
     volume = {35},
     number = {1},
     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
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
%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/

[1] Lozhkin S. A., Shupletsov M. S., “O dinamicheskoi aktivnosti skhem iz funktsionalnykh elementov i postroenii asimptoticheski optimalnykh po slozhnosti skhem s lineinoi dinamicheskoi aktivnostyu”, Uchen. zap. Kazan. un-ta. Ser. Fiz.-matem. nauki, 156:3 (2014), 84–97 | MR

[2] Sima J., “Energy complexity of recurrent neural networks”, Neural Comput., 26:5 (2014), 953–973 | DOI | MR

[3] Uchizawa K., Takimoto E., “Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity”, Theor. Comput. Sci., 407:1–3 (2008), 474–487 | DOI | MR

[4] Vaintsvaig M. N., “O moschnosti skhem iz funktsionalnykh elementov”, Doklady Akademii nauk, 139:2 (1961), 320–323 | MR

[5] Kasim-Zade O. M., “Ob odnoi mere slozhnosti skhem iz funktsionalnykh elementov”, Doklady Akademii nauk, 250:4 (1980), 797–800 | MR

[6] Kasim-Zade O. M., “Ob odnovremennoi minimizatsii slozhnosti i moschnosti skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 33 (1978), 215–220 | MR

[7] Dinesh K., Otiv S., Sarma J., “New bounds for energy complexity of Boolean functions”, Theor. Comput. Sci., 845 (2022), 59–75 | DOI | MR

[8] Lozhkin S. A., Lektsii po osnovam kibernetiki, VMK MGU, 2017