Narrow proofs may be spacious, separating space and width in resolution

DOI10.1145/1132516.1132590MaRDI QIDQ2931413zbMATH OpenOpenAlexFDO

Authors Jakob Nordstrom

Publication date 25 November 2014

Published in Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1132516.1132590

zbMATH Keywords

lower boundpebble gamepebbling contradictionproof complexityresolutionseparationspace of a proofwidth of a proof

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Narrow proofs may be spacious: separating space and width in resolution
• scientific article; zbMATH DE number 1424047
• From small space to small width in resolution
• Towards an optimal separation of space and length in resolution
• Narrow proofs may be maximally long

Cited in

(8)

• Cliques enumeration and tree-like resolution proofs
• A tutorial on time and space bounds in tree-like resolution
• Revisiting space in proof complexity: treewidth and pathwidth
• Towards an optimal separation of space and length in resolution
• Narrow proofs may be spacious: separating space and width in resolution
• Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
• The depth of resolution proofs
• Pebble games and algebraic proof systems

This page was built for publication: Narrow proofs may be spacious, separating space and width in resolution

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