On the complexity of realizations of Boolean functions in some classes of hypercontact circuits

Yu. G. Tarazevich

Diskretnaya Matematika, Tome 34 (2022) no. 3, pp. 90-113

Résumé

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.

Détail

Keywords: polynomial with idempotent variables, hypercontact circuit, contact hypergraph, contact matroid, incidence-linking matrix, contact-transformer circuit