Space bounds for resolution

DOI10.1006/inco.2001.2921zbMath1005.03009OpenAlexW2071347463MaRDI QIDQ1854472

Juan Luis Esteban, Jacobo Toran

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2001.2921

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20)

Related Items

On space and depth in resolution ⋮ On the complexity of resolution with bounded conjunctions ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ A note about \(k\)-DNF resolution ⋮ Space Complexity in Polynomial Calculus ⋮ The impact of heterogeneity and geometry on the proof complexity of random satisfiability ⋮ Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ Cliques enumeration and tree-like resolution proofs ⋮ The depth of resolution proofs ⋮ A characterization of tree-like resolution size ⋮ On semantic cutting planes with very small coefficients ⋮ A combinatorial characterization of resolution width ⋮ The treewidth of proofs ⋮ Space proof complexity for random 3-CNFs ⋮ A simplified way of proving trade-off results for resolution ⋮ The Complexity of Propositional Proofs ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ Reversible pebble games and the relation between tree-like and general resolution space ⋮ Supercritical Space-Width Trade-offs for Resolution ⋮ A combinatorial characterization of treelike resolution space ⋮ Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space ⋮ Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers ⋮ A Tutorial on Time and Space Bounds in Tree-Like Resolution ⋮ Autonomous Resolution Based on DNA Strand Displacement ⋮ Total Space in Resolution

Cites Work

• The intractability of resolution
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• Short proofs are narrow—resolution made simple
• Space complexity in propositional calculus
• Many hard examples for resolution
• Hard examples for resolution
• Lower bounds for resolution and cutting plane proofs and monotone computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Space bounds for resolution