Revisiting space in proof complexity: treewidth and pathwidth

DOI10.1007/978-3-642-40313-2_62MaRDI QIDQ2849955zbMATH OpenOpenAlexFDO

Authors Moritz Müller, Stefan Szeider

Publication date 20 September 2013

Published in Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-40313-2_62

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• The treewidth of proofs
• Narrow proofs may be spacious: separating space and width in resolution
• Short proofs are narrow—resolution made simple
• Narrow proofs may be spacious, separating space and width in resolution
• From small space to small width in resolution

Cited in

(1)

• The treewidth of proofs

This page was built for publication: Revisiting space in proof complexity: treewidth and pathwidth

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