Total space in resolution

DOI10.1137/15M1023269MaRDI QIDQ2829448zbMATH OpenWikidataFDO

Authors Ilario Bonacina, Nicola Galesi, 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)

Recommendations

• Total space in resolution is at least width squared
• scientific article; zbMATH DE number 1424047
• Space proof complexity for random 3-CNFs
• Space bounds for resolution
• From small space to small width in resolution

Cites work

• scientific article; zbMATH DE number 1470716 (Why is no real title available?)
• A combinatorial characterization of resolution width
• A framework for space complexity in algebraic proof systems
• Narrow proofs may be spacious: separating space and width in resolution
• On the complexity of resolution with bounded conjunctions
• Pebble games, proof complexity, and time-space trade-offs
• Short proofs are narrow—resolution made simple
• Space complexity in polynomial calculus
• Space Complexity in Propositional Calculus
• Space bounds for resolution
• Space complexity of random formulae in resolution
• Space proof complexity for random 3-CNFs
• The relative efficiency of propositional proof systems
• Total space in resolution
• Total space in resolution is at least width squared
• Towards an optimal separation of space and length in resolution
• Towards an understanding of polynomial calculus: new separations and lower bounds (extended abstract)
• Unified Characterisations of Resolution Hardness Measures

Cited in

(14)

• 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 is at least width squared
• Cumulative space in black-white pebbling and resolution
• Trade-offs between time and memory in a tighter model of CDCL SAT solvers
• Total space in resolution
• Space Complexity in Polynomial Calculus
• Supercritical space-width trade-offs for resolution
• Narrow proofs may be maximally long
• On space and depth in resolution
• A framework for space complexity in algebraic proof systems
• Space complexity of random formulae in resolution
• An Upper Bound on the Space Complexity of Random Formulae in Resolution

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)