The depth of resolution proofs

DOI10.1007/S11225-011-9356-9MaRDI QIDQ647405zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

proof complexityresolution proofsdepth of proofs

Mathematics Subject Classification ID

Complexity of proofs (03F20)

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 DE number 5613975

Cites work

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

Cited in

(10)

• Resolution over linear equations modulo two
• A Logical Autobiography
• Reversible pebble games and the relation between tree-like and general resolution space
• Theory and Applications of Satisfiability Testing
• 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
• On space and depth in resolution
• Cutting planes width and the complexity of graph isomorphism refutations
• Preliminary Report on Input Cover Number as a Metric for Propositional Resolution Proofs

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)