The limits of tractability in resolution-based propositional proof systems
From MaRDI portal
Publication:408157
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
Related Items (1)
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