Narrow proofs may be spacious

DOI10.1145/1132516.1132590zbMath1301.03060OpenAlexW1978701879MaRDI QIDQ2931413

Jakob Nordström

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 boundresolutionseparationproof complexitypebble gamepebbling contradictionspace of a proofwidth of a proof

Mathematics Subject Classification ID

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

Related Items (3)

Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution ⋮ Cliques enumeration and tree-like resolution proofs ⋮ The depth of resolution proofs

This page was built for publication: Narrow proofs may be spacious