A 3n-lower bound on the network complexity of Boolean functions

DOI10.1016/0304-3975(80)90074-2zbMath0438.68012OpenAlexW2045766836WikidataQ126439203 ScholiaQ126439203MaRDI QIDQ1142030

Claus Peter Schnorr

Publication date: 1980

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

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90074-2

zbMATH Keywords

Boolean functionsnetwork complexitylowerboundunrestricted binary networks

Mathematics Subject Classification ID

Related Items (8)

Nonlinear lower bounds on the number of processors of circuits with sublinear separators ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ Parity, circuits, and the polynomial-time hierarchy ⋮ The multiplicative complexity of quadratic boolean forms ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ A Boolean function requiring 3n network size ⋮ The complexity of the standard multiplexer function in a class of switching circuits ⋮ Linear lower bounds on unbounded fan-in Boolean circuits

Cites Work

• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• The combinational complexity of equivalence
• The network complexity and the Turing machine complexity of finite functions
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• On the combinational complexity of certain symmetric Boolean functions
• Unnamed Item
• Unnamed Item

This page was built for publication: A 3n-lower bound on the network complexity of Boolean functions