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