|
This article is cited in 2 scientific papers (total in 2 papers)
Minimal contact circuits for characteristic functions of spheres
N. P. Red'kin Lomonosov Moscow State University
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.
Keywords:
Boolean function, contact circuit, minimal circuit.
Received: 28.11.2019
Citation:
N. P. Red'kin, “Minimal contact circuits for characteristic functions of spheres”, Diskr. Mat., 32:3 (2020), 68–75; Discrete Math. Appl., 31:6 (2021), 403–408
Linking options:
https://www.mathnet.ru/eng/dm1601https://doi.org/10.4213/dm1601 https://www.mathnet.ru/eng/dm/v32/i3/p68
|
|