Time-space tradeoffs in resolution
From MaRDI portal
Publication:5415477
DOI10.1145/2213977.2213999zbMath1286.68180OpenAlexW2074834475MaRDI QIDQ5415477
Christopher Beck, Russell Impagliazzo, P. W. Beame
Publication date: 13 May 2014
Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2213977.2213999
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (11)
Characterizing Tseitin-Formulas with Short Regular Resolution Refutations ⋮ From Small Space to Small Width in Resolution ⋮ Narrow Proofs May Be Maximally Long ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ Strong ETH and resolution via games and the multiplicity of strategies ⋮ Space Complexity in Polynomial Calculus ⋮ An Introduction to Lower Bounds on Resolution Proof Systems ⋮ The treewidth of proofs ⋮ Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Characterizing Tseitin-formulas with short regular resolution refutations
This page was built for publication: Time-space tradeoffs in resolution