Geodesic
A lower bound for the complexity of the realization of a Boolean function by two-layer switching circuits on a plane integral lattice
Diskretnaya Matematika, Tome 9 (1997) no. 2, pp. 40-52

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_1997_9_2_a3,
     author = {O. A. Zadorozhnyuk},
     title = {A lower bound for the complexity of the realization of a {Boolean} function by two-layer switching circuits on a plane integral lattice},
     journal = {Diskretnaya Matematika},
     pages = {40--52},
     publisher = {mathdoc},
     volume = {9},
     number = {2},
     year = {1997},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1997_9_2_a3/}
}
TY  - JOUR
AU  - O. A. Zadorozhnyuk
TI  - A lower bound for the complexity of the realization of a Boolean function by two-layer switching circuits on a plane integral lattice
JO  - Diskretnaya Matematika
PY  - 1997
SP  - 40
EP  - 52
VL  - 9
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1997_9_2_a3/
LA  - ru
ID  - DM_1997_9_2_a3
ER  - 
%0 Journal Article
%A O. A. Zadorozhnyuk
%T A lower bound for the complexity of the realization of a Boolean function by two-layer switching circuits on a plane integral lattice
%J Diskretnaya Matematika
%D 1997
%P 40-52
%V 9
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1997_9_2_a3/
%G ru
%F DM_1997_9_2_a3
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. Diskretnaya Matematika, Tome 9 (1997) no. 2, pp. 40-52. http://geodesic.mathdoc.fr/item/DM_1997_9_2_a3/