RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., Ser. 1, 2007 Volume 14, Issue 1, Pages 45–69 (Mi da41)

This article is cited in 3 papers

On the depth of Boolean functions over an arbitrary infinite basis

O. M. Kasim-zade

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: Realization of Boolean functions by circuits is considered over an arbitrary infinite complete basis. The depth of a circuit is defined as the greatest number of functional elements constituting a directed path from an input of the circuit to its output. The Shannon function of the depth is defined for a positive integer $n$ as the minimal depth $D_B(n)$ of the circuits sufficient to realize every Boolean function on $n$ variables over a basis $B$. It is shown that, for each infinite basis $B$, either there exists a constant $\beta\geqslant 1$ such that $D_B(n)=\beta$ for all sufficiently large $n$ or there exist an integer constant $\gamma\geqslant 2$ and a constant $\delta$ such that $\log_\gamma n\geqslant D_B(n)\geqslant\log_\gamma n+\delta$ for all $n$.


 English version:
Journal of Applied and Industrial Mathematics, 2008, 2:2, 196–210

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025