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

DOI10.1016/0304-3975(80)90074-2MaRDI QIDQ1142030zbMATH OpenOpenAlexWikidataFDO

Authors 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

Analysis of algorithms and problem complexity (68Q25)

Cites work

• scientific article; zbMATH DE number 3695102 (Why is no real title available?)
• scientific article; zbMATH DE number 3607492 (Why is no real title available?)
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• On the combinational complexity of certain symmetric Boolean functions
• The combinational complexity of equivalence
• The network complexity and the Turing machine complexity of finite functions
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen

Cited in

(8)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1142030)