Abstract:
We study the complexity of implementation of the characteristic functions of spheres by contact circuits. By the characteristic functions of the sphere with center at a vertex $\tilde\sigma=(\sigma_1,\ldots,\sigma_n)$, $\sigma_1,\ldots,\sigma_n\in\{0,1\}$, we mean the Boolean function $\varphi^{(n)}_{\tilde\sigma}(x_1,\ldots,x_n)$ which is equal to 1 on those and only those tuples of values that differ from the tuple $\tilde\sigma$ only in one digit. It is shown that the number $3n-2$ of contacts is necessary and sufficient for implementation of $\varphi^{(n)}_{\tilde\sigma}(\tilde x)$ by a contact circuit.
Fulltext:
PDF file (425 kB)