Total Space in Resolution
From MaRDI portal
Publication:2829448
DOI10.1137/15M1023269zbMath1402.03080WikidataQ61732563 ScholiaQ61732563MaRDI QIDQ2829448
Nicola Galesi, Ilario Bonacina, Neil Thapen
Publication date: 28 October 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Related Items (9)
Narrow Proofs May Be Maximally Long ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ Space Complexity in Polynomial Calculus ⋮ Space proof complexity for random 3-CNFs ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ Supercritical Space-Width Trade-offs for Resolution ⋮ Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers ⋮ Resolution and the binary encoding of combinatorial principles ⋮ Total Space in Resolution
Cites Work
- Unnamed Item
- Unnamed Item
- Space bounds for resolution
- On the complexity of resolution with bounded conjunctions
- Space proof complexity for random 3-CNFs
- A combinatorial characterization of resolution width
- A Framework for Space Complexity in Algebraic Proof Systems
- Total Space in Resolution
- Pebble Games, Proof Complexity, and Time-Space Trade-offs
- Space Complexity in Polynomial Calculus
- Space Complexity in Propositional Calculus
- Unified Characterisations of Resolution Hardness Measures
- The relative efficiency of propositional proof systems
- Short proofs are narrow—resolution made simple
- Space complexity of random formulae in resolution
- Total Space in Resolution Is at Least Width Squared
- Narrow Proofs May Be Spacious:Separating Space and Width in Resolution
- Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
This page was built for publication: Total Space in Resolution
