An Introduction to Lower Bounds on Resolution Proof Systems
From MaRDI portal
Publication:5135261
DOI10.4036/IIS.2015.L.02zbMATH Open1486.03097OpenAlexW2185133332MaRDI QIDQ5135261FDOQ5135261
Authors: Kazuhisa Seto 
Publication date: 19 November 2020
Published in: Interdisciplinary Information Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4036/iis.2015.l.02
Recommendations
- A feasibly constructive lower bound for resolution proofs
- scientific article; zbMATH DE number 4182873
- scientific article; zbMATH DE number 886137
- scientific article; zbMATH DE number 1361471
- Lower bounds for resolution and cutting plane proofs and monotone computations
- The limits of tractability in resolution-based propositional proof systems
- The limits of tractability in resolution-based propositional proof systems
- scientific article; zbMATH DE number 549996
- Complexity of resolution proofs and function introduction
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Hard examples for resolution
- The relative efficiency of propositional proof systems
- The Complexity of Propositional Proofs
- Many hard examples for resolution
- Short proofs are narrow—resolution made simple
- The intractability of resolution
- Resolution lower bounds for perfect matching principles
- Twelve Problems in Proof Complexity
- Towards NP-P via proof complexity and search
- Title not available (Why is that?)
- The Complexity of Propositional Proofs
- Space Complexity in Propositional Calculus
- A lower bound on the size of resolution proofs of the Ramsey theorem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Resolution proofs of generalized pigeonhole principles
- Strong ETH holds for regular resolution
- Space complexity of random formulae in resolution
- Narrow proofs may be spacious: separating space and width in resolution
- Title not available (Why is that?)
- A simplified way of proving trade-off results for resolution
- Title not available (Why is that?)
- Resolution lower bounds for the weak pigeonhole principle
- Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
- Pebble games, proof complexity, and time-space trade-offs
- On the Relative Strength of Pebbling and Resolution
- Time-space tradeoffs in resolution, superpolynomial lower bounds for superlinear space
Cited In (6)
- The proof-search problem between bounded-width resolution and bounded-degree semi-algebraic proofs
- A feasibly constructive lower bound for resolution proofs
- The Complexity of Propositional Proofs
- A tutorial on time and space bounds in tree-like resolution
- A (biased) proof complexity survey for SAT practitioners
- Tight rank lower bounds for the Sherali-Adams proof system
This page was built for publication: An Introduction to Lower Bounds on Resolution Proof Systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5135261)
