Pebble Games, Proof Complexity, and Time-Space Trade-offs
From MaRDI portal
Publication:2848360
DOI10.2168/LMCS-9(3:15)2013zbMath1285.03070arXiv1307.3913OpenAlexW3101351575MaRDI QIDQ2848360
Publication date: 26 September 2013
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1307.3913
survey papercutting planesresolutionseparationpolynomial calculusproof complexitySAT solvingDPLLPCRproof sizepebble gamesCDCLproof space\(k\)-DNF resolutionpebbling formulassize-space trade-offs
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of proofs (03F20)
Related Items (22)
On space and depth in resolution ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ Unnamed Item ⋮ A note about \(k\)-DNF resolution ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ Space Complexity in Polynomial Calculus ⋮ On CDCL-Based Proof Systems with the Ordered Decision Strategy ⋮ Token Swapping on Trees ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ Cliques enumeration and tree-like resolution proofs ⋮ An Introduction to Lower Bounds on Resolution Proof Systems ⋮ On semantic cutting planes with very small coefficients ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Supercritical Space-Width Trade-offs for Resolution ⋮ Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space ⋮ Propositional proof complexity ⋮ Unnamed Item ⋮ Total Space in Resolution ⋮ Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Generalising unit-refutation completeness and SLUR via nested input resolution
This page was built for publication: Pebble Games, Proof Complexity, and Time-Space Trade-offs
