On the Complexity and Depth of Embedded in Boolean Cube Circuits That Implement Boolean Functions

摘要

A class of circuits of functional elements over the standard basis of the conjunction, disjunction, and negation elements is considered. For each circuit Σ in this class, its depth D (Σ) and dimension R (Σ) equal to the minimum dimension of the Boolean cube allowing isomorphic embedding Σ are defined. It is established that for n = 1, 2,… and an arbitrary Boolean function f of n variables there exists a circuit Σ~( f )for implementing this function such that R (Σ~( f )) ⩽ n − log~(2)log~(2) n + O (1) and D (Σ~( f )) ⩽ 2 n − 2 log~(2)log~(2) n + O (1). It is proved that for n = 1, 2,… almost all functions of n variables allow implementation by circuits of the considered type, whose depth and dimension differ from the minimum values of these parameters (for all equivalent circuits) by no more than a constant and asymptotically no more than by a factor of 2, respectively.