An improved complexity hierarchy on the depth of Boolean functions
type: Item
instance of: scholarly article
title: An improved complexity hierarchy on the depth of Boolean functions
zbMATH Open document ID: 0431.94058
DOI: 10.1007/BF00288962
author: Ingo Wegener
published in: Acta Informatica
publication date: 1981-01-01T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3672217
zbMATH Keywords: complexity hierarchy
zbMATH Keywords: complexity measures for Boolean functions
zbMATH Keywords: circuit complexity
zbMATH Keywords: depth
zbMATH Keywords: nondegenerate Boolean functions
MaRDI profile type: Publication
cites work: Lattice Theoretic Properties of Frontal Switching Functions
full work available at URL: https://doi.org/10.1007/bf00288962
OpenAlex ID: W2087109905
description: scientific article; zbMATH DE number 3672217