An improved complexity hierarchy on the depth of Boolean functions (Q1138531)

Hierarchy results play an important role in complexity theory. In this paper we consider the problem of computing Boolean functions \(f: \{0,1\}^n\to \{0,1\}\) in Boolean circuits over some binary basis \(\Omega\subseteq \{f: \{0,1\}^2\to \{0,1\}\,\}\). There are two important complexity measures for Boolean functions: (computational) circuit complexity and depth. Since very little is known about these complexity measures for explicitly defined Boolean functions one is interested in results about the behavior of these complexity measures. In this paper we prove the best possible hierarchy result on the depth of all nondegenerate Boolean functions. Let some Boolean function of \(n\) variables have depth \(k\) according to \(\Omega\). For each \(j\) where \(\lceil \log n\rceil \leq j\leq k\) we prove the existence of a Boolean function \(f\) which depends essentially on \(n\) variables and whose depth according to \(\Omega\) is exactly \(j\).