Abstract:
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.
Key words:Boolean function, circuit, complexity of a function.
Fulltext:
PDF file (308 kB)