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.