Narrow Proofs May Be Spacious:Separating Space and Width in Resolution

DOI10.1137/060668250zbMath1192.03042OpenAlexW2985351939MaRDI QIDQ5189540

Jakob Nordström

Publication date: 17 March 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060668250

zbMATH Keywords

widthlower boundresolutionseparationproof complexityspacepebble gamepebbling contradiction

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (11)

Cumulative Space in Black-White Pebbling and Resolution ⋮ Space Complexity in Polynomial Calculus ⋮ An Introduction to Lower Bounds on Resolution Proof Systems ⋮ On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution ⋮ The treewidth of proofs ⋮ Space proof complexity for random 3-CNFs ⋮ A simplified way of proving trade-off results for resolution ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ Supercritical Space-Width Trade-offs for Resolution ⋮ Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space ⋮ Total Space in Resolution

This page was built for publication: Narrow Proofs May Be Spacious:Separating Space and Width in Resolution