Volume 3 (2007) Article 5 pp. 81-102

An Exponential Separation between Regular and General Resolution

by Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, and Alasdair Urquhart

Received: August 15, 2006
Published: May 1, 2007

Download article from ToC site:
[PDF (220K)]    [PS (399K)]    [PS.GZ (104K)]    [PS.ZIP (104K)]
[Source ZIP (55K)]
Misc.:
[About the Author(s)] [HTML Bibliography] [BibTeX]
Keywords: resolution, proof complexity, lower bounds
Categories: complexity theory, 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.

DOI: 10.4086/toc.2007.v003a005
© 2007 Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, and Alasdair Urquhart
Creative Commons License Licensed under a Creative Commons License