An exponential lower bound for the size of monotone real circuits

DOI10.1006/jcss.1998.1617zbMath0922.68065OpenAlexW2083193613MaRDI QIDQ1288204

Armin Haken, Stephen A. Cook

Publication date: 11 May 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1998.1617

zbMATH Keywords

unrestricted cutting plane proofs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes ⋮ On the automatizability of resolution and related propositional proof systems ⋮ Dag-like communication and its applications ⋮ A note on monotone real circuits ⋮ On reducibility and symmetry of disjoint NP pairs. ⋮ Lifting lower bounds for tree-like proofs ⋮ On the complexity of cutting-plane proofs using split cuts ⋮ Unnamed Item

Cites Work

• On the complexity of cutting-plane proofs
• The intractability of resolution
• The monotone circuit complexity of Boolean functions
• Many hard examples for resolution
• Hard examples for resolution
• Lower bounds for resolution and cutting plane proofs and monotone computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An exponential lower bound for the size of monotone real circuits