A simplified way of proving trade-off results for resolution
From MaRDI portal
Publication:989569
DOI10.1016/J.IPL.2009.06.006zbMATH Open1202.68388OpenAlexW2109895531MaRDI QIDQ989569FDOQ989569
Authors: Jakob Nordstrom 
Publication date: 20 August 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2009.06.006
Recommendations
computational complexityresolutionlengthproof complexityautomatic theorem provingwidthspacetrade-offs
Cites Work
- The complexity of facets resolved
- Title not available (Why is that?)
- Hard examples for resolution
- Short proofs are narrow—resolution made simple
- Space Complexity in Propositional Calculus
- Space bounds for resolution
- A combinatorial characterization of resolution width
- Optimality of size-width tradeoffs for resolution
- Short resolution proofs for a sequence of tricky formulas
- Space complexity of random formulae in resolution
- Title not available (Why is that?)
- Narrow proofs may be spacious: separating space and width in resolution
- Title not available (Why is that?)
Cited In (8)
- A tradeoff between length and width in resolution
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- An Introduction to Lower Bounds on Resolution Proof Systems
- Nullstellensatz size-degree trade-offs from reversible pebbling
- From small space to small width in resolution
- Contradiction separation based dynamic multi-clause synergized automated deduction
- Space Complexity in Polynomial Calculus
- Strong extension-free proof systems
This page was built for publication: A simplified way of proving trade-off results for resolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989569)
