A Tutorial on Time and Space Bounds in Tree-Like Resolution

DOI10.1007/978-3-319-05446-9_9zbMath1345.03109OpenAlexW151848869MaRDI QIDQ2821700

Jacobo Toran

Publication date: 22 September 2016

Published in: Perspectives in Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-05446-9_9

zbMATH Keywords

resolutioncombinatorial games

Mathematics Subject Classification ID

Logic in computer science (03B70) Mechanization of proofs and logical operations (03B35) Combinatorial games (91A46) Complexity of proofs (03F20)

Cites Work

• Near optimal seperation of tree-like and general resolution
• A combinatorial characterization of treelike resolution space
• The intractability of resolution
• A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
• Space bounds for resolution
• A characterization of tree-like resolution size
• On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
• Space Complexity in Propositional Calculus
• Many hard examples for resolution
• Hard examples for resolution
• A Machine-Oriented Logic Based on the Resolution Principle

This page was built for publication: A Tutorial on Time and Space Bounds in Tree-Like Resolution