Optimality of size-width tradeoffs for resolution
From MaRDI portal
Publication:1405735
DOI10.1007/s000370100000zbMath1024.03012DBLPjournals/cc/BonetG01OpenAlexW2084029169WikidataQ60512234 ScholiaQ60512234MaRDI QIDQ1405735
Maria Luisa Bonet, Nicola Galesi
Publication date: 26 August 2003
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s000370100000
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (17)
Narrow Proofs May Be Maximally Long ⋮ On the automatizability of resolution and related propositional proof systems ⋮ A note about \(k\)-DNF resolution ⋮ Width versus size in resolution proofs ⋮ Regular and General Resolution: An Improved Separation ⋮ Space characterizations of complexity measures and size-space trade-offs in propositional proof systems ⋮ Cliques enumeration and tree-like resolution proofs ⋮ Automatizability and Simple Stochastic Games ⋮ A combinatorial characterization of resolution width ⋮ The treewidth of proofs ⋮ A simplified way of proving trade-off results for resolution ⋮ Parameterized Complexity of DPLL Search Procedures ⋮ An Exponential Lower Bound for Width-Restricted Clause Learning ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs ⋮ Sum of squares bounds for the ordering principle ⋮ Resolution and the binary encoding of combinatorial principles ⋮ On Linear Resolution
This page was built for publication: Optimality of size-width tradeoffs for resolution