Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
From MaRDI portal
Publication:1220384
DOI10.1007/BF02246615zbMath0313.68033MaRDI QIDQ1220384
Publication date: 1974
Published in: Computing (Search for Journal in Brave)
Related Items
On the limits of gate elimination ⋮ Correlation bounds and \#SAT algorithms for small linear-size circuits ⋮ Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits ⋮ Lower Bounds for the Size of Nondeterministic Circuits ⋮ The circuit complexity of checking polynomiality for functions over residue ring modulo a composite number is linear ⋮ A 3n-lower bound on the network complexity of Boolean functions ⋮ Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables ⋮ On compiling Boolean circuits optimized for secure multi-party computation ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Size bounds for superconcentrators ⋮ On the power of nondeterministic circuits and co-nondeterministic circuits ⋮ The complexity of the parity function in unbounded fan-in, unbounded depth circuits ⋮ Nonlinear lower bounds on the number of processors of circuits with sublinear separators ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ Reductions for monotone Boolean circuits ⋮ A class of Boolean functions with linear combinational complexity ⋮ On the combinational complexity of certain symmetric Boolean functions ⋮ The combinational complexity of equivalence ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ Unnamed Item ⋮ On Negations in Boolean Networks ⋮ A Boolean function requiring 3n network size ⋮ Nearly optimal hierarchies for network and formula size ⋮ An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution ⋮ Linear lower bounds on unbounded fan-in Boolean circuits ⋮ Upper estimate of realization complexity of linear functions in a basis consisting of multi-input elements ⋮ New lower bounds on circuit size of multi-output functions
Cites Work
