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

DOI10.1016/0304-3975(91)90052-4zbMath0749.94025MaRDI 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 measure; Boolean function complexity theory; complexity of the parity function; unbounded fan-in Boolean circuits

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

Related Items

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

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