Some trade-off results for polynomial calculus

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

zbMATH Keywords

degreeresolutionpolynomial calculusproof complexityPCRTseitin formulaspebble gamespebbling formulassize-space trade-offs

Mathematics Subject Classification ID

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

• PolyBoRi

This page was built for publication: Some trade-off results for polynomial calculus