The complexity of the parity function in unbounded fan-in, unbounded depth circuits

DOI10.1016/0304-3975(91)90052-4zbMath0749.94025OpenAlexW1967516941MaRDI QIDQ1183575

Ingo Wegener

Publication date: 28 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90052-4

zbMATH Keywords

complexity measureBoolean function complexity theorycomplexity of the parity functionunbounded fan-in Boolean circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Lower bound of circuit complexity of parity function in a basis of unbounded fan-in ⋮ On the complexity of encoding in analog circuits ⋮ Size-energy tradeoffs for unate circuits computing symmetric Boolean functions ⋮ Some notes on threshold circuits, and multiplication in depth 4 ⋮ Complexity and structure of circuits for parity functions ⋮ On the positive and the inversion complexity of Boolean functions ⋮ Upper estimate of realization complexity of linear functions in a basis consisting of multi-input elements

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• Constant Depth Reducibility
• On bounds for complexity of circuits of multi-input functional elements
• Logic Networks with a Minimum Number of NOR(NAND) Gates for Parity Functions of n Variables