Total space in resolution
From MaRDI portal
Publication:2829448
DOI10.1137/15M1023269zbMATH Open1402.03080WikidataQ61732563 ScholiaQ61732563MaRDI QIDQ2829448FDOQ2829448
Nicola Galesi, Ilario Bonacina, Neil Thapen
Publication date: 28 October 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The relative efficiency of propositional proof systems
- Short proofs are narrow—resolution made simple
- Space Complexity in Propositional Calculus
- Space bounds for resolution
- On the complexity of resolution with bounded conjunctions
- A combinatorial characterization of resolution width
- Space complexity of random formulae in resolution
- Narrow Proofs May Be Spacious:Separating Space and Width in Resolution
- Total space in resolution
- Pebble games, proof complexity, and time-space trade-offs
- Total Space in Resolution Is at Least Width Squared
- A framework for space complexity in algebraic proof systems
- Space Complexity in Polynomial Calculus
- Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
- Space proof complexity for random 3-CNFs
- Unified Characterisations of Resolution Hardness Measures
Cited In (11)
- Resolution and the binary encoding of combinatorial principles
- Proof complexity and the binary encoding of combinatorial principles
- Space proof complexity for random 3-CNFs
- Total space in resolution
- Narrow Proofs May Be Maximally Long
- Space Complexity in Polynomial Calculus
- Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers
- Supercritical Space-Width Trade-offs for Resolution
- On space and depth in resolution
- Cumulative Space in Black-White Pebbling and Resolution
- A framework for space complexity in algebraic proof systems
This page was built for publication: Total space in resolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2829448)