The limits of tractability in resolution-based propositional proof systems
From MaRDI portal
Recommendations
- The limits of tractability in resolution-based propositional proof systems
- The intractability of resolution
- On the automatizability of resolution and related propositional proof systems
- Relativization makes contradictions harder for resolution
- Relativisation Provides Natural Separations for Resolution-Based Proof Systems
Cites work
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- A complexity gap for tree resolution
- Computer Science Logic
- Lower bounds to the size of constant-depth propositional proofs
- On the weak pigeonhole principle
- Probability and Computing
- Proofs as Games
- Rank bounds and integrality gaps for cutting planes procedures
- Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
- Separation results for the size of constant-depth propositional proofs
- Short proofs for tricky formulas
- The limits of tractability in resolution-based propositional proof systems
- The provably total search problems of bounded arithmetic
Cited in
(7)- scientific article; zbMATH DE number 1765669 (Why is no real title available?)
- The rue theorem-proving system: The complete set of LIM+ challenge problems
- The limits of tractability in resolution-based propositional proof systems
- The treewidth of proofs
- Relativization makes contradictions harder for resolution
- An Introduction to Lower Bounds on Resolution Proof Systems
- NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability
This page was built for publication: The limits of tractability in resolution-based propositional proof systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q408157)
