An Introduction to Lower Bounds on Resolution Proof Systems
From MaRDI portal
Publication:5135261
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
- scientific article; zbMATH DE number 1223618 (Why is no real title available?)
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1304340 (Why is no real title available?)
- scientific article; zbMATH DE number 1775444 (Why is no real title available?)
- scientific article; zbMATH DE number 1860652 (Why is no real title available?)
- scientific article; zbMATH DE number 5485584 (Why is no real title available?)
- scientific article; zbMATH DE number 3313427 (Why is no real title available?)
- A lower bound on the size of resolution proofs of the Ramsey theorem
- A simplified way of proving trade-off results for resolution
- Hard examples for resolution
- Many hard examples for resolution
- Narrow proofs may be spacious: separating space and width in resolution
- On the Relative Strength of Pebbling and Resolution
- Pebble games, proof complexity, and time-space trade-offs
- Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
- Resolution lower bounds for perfect matching principles
- Resolution lower bounds for the weak pigeonhole principle
- Resolution proofs of generalized pigeonhole principles
- Short proofs are narrow—resolution made simple
- Space Complexity in Propositional Calculus
- Space complexity of random formulae in resolution
- Strong ETH holds for regular resolution
- The Complexity of Propositional Proofs
- The Complexity of Propositional Proofs
- The intractability of resolution
- The relative efficiency of propositional proof systems
- Time-space tradeoffs in resolution, superpolynomial lower bounds for superlinear space
- Towards NP-P via proof complexity and search
- Twelve Problems in Proof Complexity
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)
