Optimality of size-width tradeoffs for resolution

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

zbMATH Keywords

resolutioncomplexity of proofsautomated theorem proving

Mathematics Subject Classification ID

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