Models of lower-bounds proofs

DOI10.1016/0304-3975(87)90110-1MaRDI QIDQ1107322zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 51644
• Natural proofs
• Natural proofs
• scientific article; zbMATH DE number 139642
• scientific article; zbMATH DE number 2102736

Cites work

• scientific article; zbMATH DE number 3916179 (Why is no real title available?)
• scientific article; zbMATH DE number 3941436 (Why is no real title available?)
• scientific article; zbMATH DE number 3566175 (Why is no real title available?)
• scientific article; zbMATH DE number 194333 (Why is no real title available?)
• scientific article; zbMATH DE number 3285250 (Why is no real title available?)
• scientific article; zbMATH DE number 3422273 (Why is no real title available?)
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• A Boolean function requiring 3n network size
• On the combinational complexity of certain symmetric Boolean functions
• The combinational complexity of equivalence
• Universal circuits (Preliminary Report)

Cited in

(5)

• Natural proofs
• scientific article; zbMATH DE number 3916179 (Why is no real title available?)
• scientific article; zbMATH DE number 4059378 (Why is no real title available?)
• scientific article; zbMATH DE number 51644 (Why is no real title available?)
• scientific article; zbMATH DE number 139642 (Why is no real title available?)

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

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