The depth of resolution proofs

DOI10.1007/s11225-011-9356-9zbMath1259.03074OpenAlexW2083975113MaRDI QIDQ647405

Alasdair Urquhart

Publication date: 23 November 2011

Published in: Studia Logica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11225-011-9356-9

zbMATH Keywords

proof complexityresolution proofsdepth of proofs

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (5)

On space and depth in resolution ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ Reversible pebble games and the relation between tree-like and general resolution space ⋮ Resolution over linear equations modulo two ⋮ A Logical Autobiography

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Near optimal seperation of tree-like and general resolution
• A combinatorial characterization of treelike resolution space
• Space bounds for resolution
• On the complexity of resolution with bounded conjunctions
• Separation of the monotone NC hierarchy
• Relationships between nondeterministic and deterministic tape complexities
• On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
• Narrow proofs may be spacious
• Space Complexity in Propositional Calculus
• Regular and General Resolution: An Improved Separation
• An exponential separation between regular and general resolution
• Size space tradeoffs for resolution
• Space bounds for a game on graphs
• Short proofs are narrow—resolution made simple
• Search Problems in the Decision Tree Model
• The Complexity of Propositional Proofs

This page was built for publication: The depth of resolution proofs