Size-Space Tradeoffs for Resolution

DOI10.1137/080723880zbMath1191.68617OpenAlexW2164319662MaRDI QIDQ3654387

Eli Ben-Sasson

Publication date: 6 January 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080723880

zbMATH Keywords

resolutionautomated theorem proverspropositional proof complexityproof length

Mathematics Subject Classification ID

Related Items (12)

From Small Space to Small Width in Resolution ⋮ Narrow Proofs May Be Maximally Long ⋮ On space and depth in resolution ⋮ Space Complexity in Polynomial Calculus ⋮ Unnamed Item ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ Unnamed Item ⋮ The treewidth of proofs ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Supercritical Space-Width Trade-offs for Resolution ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ MaxSAT Resolution and Subcube Sums

This page was built for publication: Size-Space Tradeoffs for Resolution