Alekhnovich, Michael; Johannsen, Jan; Pitassi, Toniann; Urquhart, Alasdair An exponential separation between regular and general resolution. (English) Zbl 1213.68303 Theory Comput. 3, Paper No. 5, 81-102 (2007). Summary: This paper gives two distinct proofs of an exponential separation between regular resolution and unrestricted resolution. The previous best known separation between these systems was quasi-polynomial. Cited in 10 Documents MSC: 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 03F20 Complexity of proofs Keywords:resolution; proof complexity; lower bounds Software:Chaff; MiniSat PDF BibTeX XML Cite \textit{M. Alekhnovich} et al., Theory Comput. 3, Paper No. 5, 81--102 (2007; Zbl 1213.68303) Full Text: DOI OpenURL