A combinatorial characterization of treelike resolution space

DOI10.1016/S0020-0190(03)00345-4zbMath1161.68637OpenAlexW1998430462MaRDI QIDQ1014444

Juan Luis Esteban, Jacobo Toran

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(03)00345-4

zbMATH Keywords

theory of computationcomplexity measures for resolutiontreelike resolution

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Related Items (10)

On the complexity of resolution with bounded conjunctions ⋮ On (simple) decision tree rank ⋮ A game characterisation of tree-like Q-resolution size ⋮ 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 ⋮ Reversible pebble games and the relation between tree-like and general resolution space ⋮ A Game Characterisation of Tree-like Q-resolution Size ⋮ A Tutorial on Time and Space Bounds in Tree-Like Resolution

Cites Work

• Unnamed Item
• Unnamed Item
• The intractability of resolution
• Space bounds for resolution
• A combinatorial characterization of resolution width
• On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
• Space Complexity in Propositional Calculus
• Many hard examples for resolution
• Size space tradeoffs for resolution
• Hard examples for resolution
• Short proofs are narrow—resolution made simple
• A Machine-Oriented Logic Based on the Resolution Principle

This page was built for publication: A combinatorial characterization of treelike resolution space