Relating monotone formula size and monotone depth of Boolean functions

DOI10.1016/0020-0190(83)90011-XzbMath0504.94035MaRDI QIDQ1835900

Ingo Wegener

Publication date: 1983

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitydepthformula sizemonotone basistrade-off- results

Mathematics Subject Classification ID

Related Items (12)

A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators ⋮ Applications of matrix methods to the theory of lower bounds in computational complexity ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ Uniformity of a certain systems of functions of many-valued logic ⋮ Lower bounds for Boolean circuits of bounded negation width ⋮ Strengthening convex relaxations of 0/1-sets using Boolean formulas ⋮ Translating propositional extended conjunctions of Horn clauses into Boolean circuits ⋮ W-hierarchies defined by symmetric gates ⋮ Lower Bounds for DeMorgan Circuits of Bounded Negation Width ⋮ Monotone circuits for monotone weighted threshold functions ⋮ Replaceability and computational equivalence for monotone boolean functions ⋮ Certain sufficient conditions of uniformity for systems of functions of many-valued logic

Cites Work

• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• Unnamed Item

This page was built for publication: Relating monotone formula size and monotone depth of Boolean functions