An improved complexity hierarchy on the depth of Boolean functions
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\).
- On the depth of Boolean functions over an arbitrary infinite basis
- scientific article; zbMATH DE number 4045650
- The complexity hierarchy of Boolean bases
- An average-case depth hierarchy theorem for Boolean circuits
- On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
- On the VC-dimension of depth four threshold circuits and the complexity of Boolean-valued functions
- Depth of -completions of systems of Boolean functions.
- Amplification of Bounded Depth Monotone Read-Once Boolean Formulae
- scientific article; zbMATH DE number 1747443 (Why is no real title available?)
- An average-case depth hierarchy theorem for Boolean circuits
This page was built for publication: An improved complexity hierarchy on the depth of Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1138531)
