Some trade-off results for polynomial calculus
From MaRDI portal
Publication:5495852
DOI10.1145/2488608.2488711zbMath1293.03031OpenAlexW2134253979MaRDI QIDQ5495852
Bang-Sheng Tang, Chris Beck, Jakob Nordström
Publication date: 7 August 2014
Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2488608.2488711
degreeresolutionpolynomial calculusproof complexityPCRTseitin formulaspebble gamespebbling formulassize-space trade-offs
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (13)
From Small Space to Small Width in Resolution ⋮ Narrow Proofs May Be Maximally Long ⋮ On space and depth in resolution ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ Space Complexity in Polynomial Calculus ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ 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 ⋮ Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Computing (and Life) Is All about Tradeoffs
Uses Software
This page was built for publication: Some trade-off results for polynomial calculus
