A Near-Optimal Separation of Regular and General Resolution

DOI10.1137/090772897zbMath1222.03063OpenAlexW2065171007MaRDI QIDQ2999857

Alasdair Urquhart

Publication date: 17 May 2011

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

Full work available at URL: http://epubs.siam.org/sicomp/resource/1/smjcat/v40/i1/p107_s1

zbMATH Keywords

lower boundsresolutionproof complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (7)

Characterizing Tseitin-Formulas with Short Regular Resolution Refutations ⋮ Unnamed Item ⋮ Proofs and Certificates for Max-SAT ⋮ A Logical Autobiography ⋮ Reflections on Proof Complexity and Counting Principles ⋮ Characterizing Tseitin-formulas with short regular resolution refutations ⋮ A proof builder for Max-SAT

This page was built for publication: A Near-Optimal Separation of Regular and General Resolution