×

An exponential separation between regular and general resolution. (English) Zbl 1213.68303

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.

MSC:

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

Software:

Chaff; MiniSat
PDF BibTeX XML Cite
Full Text: DOI