On the Complexity and Depth of Embedded in Boolean Cube Circuits That Implement Boolean Functions
Sergey Andreevich Lozhkin, E. L. Dovgalyuk, O. A. Sadovnikov · Moscow University Computational Mathematics and Cybernetics · 2018
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.