An improved complexity hierarchy on the depth of Boolean functions

DOI10.1007/BF00288962MaRDI QIDQ1138531zbMATH OpenOpenAlexFDO

Authors Ingo Wegener

Publication date 1981

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00288962

zbMATH Keywords

depthcircuit complexitycomplexity measures for Boolean functionscomplexity hierarchynondegenerate Boolean functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• 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

Cites work

• Lattice Theoretic Properties of Frontal Switching Functions

Cited in

(5)

• Amplification of Bounded Depth Monotone Read-Once Boolean Formulae
• On the VC-dimension of depth four threshold circuits and the complexity of Boolean-valued functions
• An average-case depth hierarchy theorem for Boolean circuits
• Depth of \(\alpha\)-completions of systems of Boolean functions.
• scientific article; zbMATH DE number 1747443 (Why is no real title available?)

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)