A combinatorial characterization of treelike resolution space

DOI10.1016/S0020-0190(03)00345-4zbMATH Open1161.68637OpenAlexW1998430462MaRDI QIDQ1014444FDOQ1014444

Authors: Juan Luis Esteban, Jacobo Torán 

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

Recommendations

• A combinatorial characterization of resolution width
• Game Characterizations and the PSPACE-Completeness of Tree Resolution Space
• Space bounds for resolution
• From small space to small width in resolution
• scientific article; zbMATH DE number 1304340

zbMATH Keywords

theory of computationcomplexity measures for resolutiontreelike resolution

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Cites Work

• Title not available (Why is that?)
• Hard examples for resolution
• A Machine-Oriented Logic Based on the Resolution Principle
• Many hard examples for resolution
• Short proofs are narrow—resolution made simple
• The intractability of resolution
• Title not available (Why is that?)
• Space Complexity in Propositional Calculus
• Space bounds for resolution
• On the relative complexity of resolution refinements and cutting planes proof systems
• Size space tradeoffs for resolution
• A combinatorial characterization of resolution width

Cited In (14)

• On the complexity of resolution with bounded conjunctions
• Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
• Game Characterizations and the PSPACE-Completeness of Tree Resolution Space
• Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space
• On (simple) decision tree rank
• A tutorial on time and space bounds in tree-like resolution
• A characterization of tree-like resolution size
• A game characterisation of tree-like Q-resolution size
• Reversible pebble games and the relation between tree-like and general resolution space
• Title not available (Why is that?)
• A game characterisation of tree-like Q-resolution size
• The depth of resolution proofs
• Recursive properties of branching and BGG resolution
• Cliques enumeration and tree-like resolution proofs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1014444)