|
A lower bound for the complexity of the realization of a Boolean function by two-layer switching circuits on a plane integral lattice
O. A. Zadorozhnyuk
Abstract:
In this paper the complexity $L_d(f_n)$ of realization of individual Boolean functions by planar two-layer contact circuits is investigated. The functional part of such circuits contains contacts, conductors, and insulators. Besides, there is a special planar circuit containing only conductors and insulators which simulates the transmission of control actions (values of variables) to the contacts of the functional part. The area occupied by a circuit is considered as the measure of complexity. In the paper the bound of the form
$L_d(f_n)\ge Cn^2/\log_2 n$, where $C$ is a constant, is obtained for the universal Nechiporuk function.
Received: 18.10.1994 Revised: 20.02.1995
Citation:
O. A. Zadorozhnyuk, “A lower bound for the complexity of the realization of a Boolean function by two-layer switching circuits on a plane integral lattice”, Diskr. Mat., 9:2 (1997), 40–52; Discrete Math. Appl., 7:3 (1997), 243–256
Linking options:
https://www.mathnet.ru/eng/dm477https://doi.org/10.4213/dm477 https://www.mathnet.ru/eng/dm/v9/i2/p40
|
Statistics & downloads: |
Abstract page: | 371 | Full-text PDF : | 209 | First page: | 1 |
|