Volume 3 (2007)
Article 5 pp. 81-102
An Exponential Separation between Regular and General Resolution
Received: August 15, 2006
Published: May 1, 2007
Published: May 1, 2007
Keywords: resolution, proof complexity, lower bounds
ACM Classification: F.2.2., F.2.3
AMS Classification: 03F20, 68Q17
Abstract: [Plain Text Version]
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.