The depth of resolution proofs

DOI10.1007/S11225-011-9356-9zbMATH Open1259.03074OpenAlexW2083975113MaRDI QIDQ647405FDOQ647405

Authors: 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

Recommendations

• Short proofs are narrow—resolution made simple
• Narrow proofs may be spacious: separating space and width in resolution
• Narrow proofs may be spacious, separating space and width in resolution
• On space and depth in resolution
• scientific article

zbMATH Keywords

proof complexityresolution proofsdepth of proofs

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Cites Work

• Relationships between nondeterministic and deterministic tape complexities
• Short proofs are narrow—resolution made simple
• A combinatorial characterization of treelike resolution space
• An exponential separation between regular and general resolution
• The Complexity of Propositional Proofs
• Title not available (Why is that?)
• Space Complexity in Propositional Calculus
• Title not available (Why is that?)
• Title not available (Why is that?)
• Near optimal seperation of tree-like and general resolution
• Space bounds for a game on graphs
• Space bounds for resolution
• On the complexity of resolution with bounded conjunctions
• Separation of the monotone NC hierarchy
• On the relative complexity of resolution refinements and cutting planes proof systems
• Narrow proofs may be spacious, separating space and width in resolution
• Regular and General Resolution: An Improved Separation
• Size space tradeoffs for resolution
• Search Problems in the Decision Tree Model

Cited In (10)

• Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
• Understanding Resolution Proofs through Herbrand’s Theorem
• Proof complexity and textual cohesion
• Reversible pebble games and the relation between tree-like and general resolution space
• Resolution over linear equations modulo two
• Theory and Applications of Satisfiability Testing
• A Logical Autobiography
• Cutting planes width and the complexity of graph isomorphism refutations
• Preliminary Report on Input Cover Number as a Metric for Propositional Resolution Proofs
• On space and depth in resolution

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

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