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

Resumo

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₂ log₂n + O(1) and D(Σ_f) ⩽ 2n − 2 log₂ log₂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.