The limits of tractability in resolution-based propositional proof systems

DOI10.1016/j.apal.2011.11.001zbMath1251.03070OpenAlexW1521370165MaRDI QIDQ408157

Barnaby Martin, Stefan S. Dantchev

Publication date: 29 March 2012

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2011.11.001

zbMATH Keywords

lower boundspropositional proof complexityresolution with bounded conjunction

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (1)

The treewidth of proofs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Short proofs for tricky formulas
• A complexity gap for tree resolution
• Separation results for the size of constant-depth propositional proofs
• Proofs as Games
• On the weak pigeonhole principle
• The provably total search problems of bounded arithmetic
• The Limits of Tractability in Resolution-Based Propositional Proof Systems
• Lower bounds to the size of constant-depth propositional proofs
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• Computer Science Logic
• Probability and Computing

This page was built for publication: The limits of tractability in resolution-based propositional proof systems