Total Space in Resolution

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)

zbMATH Keywords

resolutionproof complexityrandom CNFstotal space

Mathematics Subject Classification ID

Complexity of proofs (03F20)

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