|
On the complexity of realizations of Boolean functions in some classes of hypercontact circuits
Yu. G. Tarazevich Belarusian State University, Minsk
Abstract:
In the classes $\operatorname{\text{EM}}_F^{(n)}$ of extended matrices over rings of polynomials with idempotent variables, the following subclasses (hypercontact circuits) are defined: $\operatorname{\text{HC}}_F^{(n)}$ (over an arbitrary field $F$) and $\operatorname{\text{HC}}_Z^{(n)}$ (over the ring of integers), which algebraically extend the class of incident matrices of contact circuits ($\operatorname{\text{CC}}^{(n)}$) and realize arbitrary $n$-place Boolean functions with contact complexity smaller than $3\sqrt{2}\cdot2^{n/2}$. A lower estimate of the same order is obtained for the corresponding Shannon function in the class $\operatorname{\text{HC}}_{F_q}^{(n)}$ over an arbitrary finite field $F_q$. For matrices from the class $\operatorname{\text{HC}}_Z^{(n)}$, we find a physical interpretation in the form of incident-linking matrices of contact-transformer circuits.
Keywords:
polynomial with idempotent variables, hypercontact circuit, contact hypergraph, contact matroid, incidence-linking matrix, contact-transformer circuit
Received: 09.02.2018 Revised: 24.12.2021
Citation:
Yu. G. Tarazevich, “On the complexity of realizations of Boolean functions in some classes of hypercontact circuits”, Diskr. Mat., 34:3 (2022), 90–113; Discrete Math. Appl., 34:1 (2024), 33–50
Linking options:
https://www.mathnet.ru/eng/dm1503https://doi.org/10.4213/dm1503 https://www.mathnet.ru/eng/dm/v34/i3/p90
|
Statistics & downloads: |
Abstract page: | 302 | Full-text PDF : | 51 | References: | 58 | First page: | 24 |
|