Models of lower-bounds proofs

DOI10.1016/0304-3975(87)90110-1zbMath0652.68061OpenAlexW1986229957MaRDI QIDQ1107322

R. G. Nigmatullin

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90110-1

zbMATH Keywords

Boolean functionsBoolean complexitylower bound proofs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20)

Cites Work

• A Boolean function requiring 3n network size
• The combinational complexity of equivalence
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• Universal circuits (Preliminary Report)
• On the combinational complexity of certain symmetric Boolean functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Models of lower-bounds proofs