On the complexity of implementation of characteristic functions of the spheres by circuits of functional elements

N. P. Red'kin

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2022), pp. 18-20

Résumé

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.