Narrow Proofs May Be Spacious:Separating Space and Width in Resolution
From MaRDI portal
Publication:5189540
DOI10.1137/060668250zbMath1192.03042OpenAlexW2985351939MaRDI QIDQ5189540
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
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