Models of lower-bounds proofs

DOI10.1016/0304-3975(87)90110-1zbMATH Open0652.68061OpenAlexW1986229957MaRDI QIDQ1107322FDOQ1107322

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

Recommendations

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

zbMATH Keywords

Boolean functionsBoolean complexitylower bound proofs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A Boolean function requiring 3n network size
• Title not available (Why is that?)
• On the combinational complexity of certain symmetric Boolean functions
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• The combinational complexity of equivalence
• Title not available (Why is that?)
• Title not available (Why is that?)
• Universal circuits (Preliminary Report)

Cited In (5)

• Natural proofs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

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)