Geodesic
On the complexity of implementation of characteristic functions of the spheres by circuits of functional elements
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2022), pp. 18-20 
N. P. Red'kin. On the complexity of implementation of characteristic functions of the spheres by circuits of functional elements. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2022), pp. 18-20. http://geodesic.mathdoc.fr/item/VMUMM_2022_3_a3/
@article{VMUMM_2022_3_a3,
     author = {N. P. Red'kin},
     title = {On the complexity of implementation of characteristic functions of the spheres by circuits of functional elements},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {18--20},
     year = {2022},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2022_3_a3/}
}
TY  - JOUR
AU  - N. P. Red'kin
TI  - On the complexity of implementation of characteristic functions of the spheres by circuits of functional elements
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2022
SP  - 18
EP  - 20
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2022_3_a3/
LA  - ru
ID  - VMUMM_2022_3_a3
ER  - 
%0 Journal Article
%A N. P. Red'kin
%T On the complexity of implementation of characteristic functions of the spheres by circuits of functional elements
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2022
%P 18-20
%N 3
%U http://geodesic.mathdoc.fr/item/VMUMM_2022_3_a3/
%G ru
%F VMUMM_2022_3_a3

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

For characteristic functions of spheres, an asymptotics for the complexity of their implementation by circuits of functional elements in the basis $\{\&,\vee,-\}$ is established; the characteristic function of a sphere with the center at the vertex $\tilde\sigma=(\sigma_1,\ldots,\sigma_n)$, $\sigma_1,\ldots,\sigma_n\in\{0,1\}$, is the Boolean function equal to one on all those and only those sets of values of variables each of which differs from the vertex $\tilde\sigma$ only in one digit.

[1] Lupanov O.B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, M., 1984

[2] Redkin N.P., “Minimalnye kontaktnye skhemy dlya kharakteristicheskikh funktsii sfer”, Diskretn. matem., 32:3 (2020), 68–75 | MR

[3] Grinchuk M.I., “O monotonnoi slozhnosti porogovykh funktsii”, Metody diskretnogo analiza v teorii grafov i slozhnosti, 1992, no. 52, 41–48 | MR

[4] Redkin N.P., “Minimalnye kontaktnye skhemy dlya simmetricheskikh porogovykh funktsii”, Matem. zametki, 108:3 (2020), 397–411 | MR | Zbl

[5] Redkin N.P., “Dokazatelstvo minimalnosti nekotorykh skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 23, Nauka, M., 1970, 83–101 | MR