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

DOI10.1137/060668250MaRDI QIDQ5189540zbMATH OpenOpenAlexFDO

Authors Jakob Nordstrom

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

lower boundpebble gamepebbling contradictionproof complexityresolutionseparationspacewidth

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) 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
• From small space to small width in resolution
• Narrow proofs may be maximally long
• From small space to small width in resolution
• Short proofs are narrow—resolution made simple

Cited in

(22)

• Space bounds for resolution
• The treewidth of proofs
• Space proof complexity for random 3-CNFs
• A combinatorial characterization of resolution width
• A framework for space complexity in algebraic proof systems
• A tradeoff between length and width in resolution
• Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
• Total space in resolution
• Revisiting space in proof complexity: treewidth and pathwidth
• Width and size of regular resolution proofs
• Narrow proofs may be spacious, separating space and width in resolution
• Space complexity in polynomial calculus
• On minimal unsatisfiability and time-space trade-offs for k-DNF resolution
• Towards an optimal separation of space and length in resolution
• Total space in resolution is at least width squared
• Cumulative space in black-white pebbling and resolution
• An Introduction to Lower Bounds on Resolution Proof Systems
• Supercritical space-width trade-offs for resolution
• Narrow proofs may be maximally long
• The depth of resolution proofs
• Towards an understanding of polynomial calculus: new separations and lower bounds
• A simplified way of proving trade-off results for resolution

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 Q5189540)