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