Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > REGULAR RESOLUTION:
Reports tagged with regular resolution:
TR98-035 | 8th May 1998
Maria Luisa Bonet, Juan Luis Esteban, Jan Johannsen

Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems

We prove an exponential lower bound for tree-like Cutting Planes
refutations of a set of clauses which has polynomial size resolution
refutations. This implies an exponential separation between tree-like
and dag-like proofs for both Cutting Planes and resolution; in both
cases only superpolynomial separations were known before.
In order to ... more >>>


TR01-056 | 6th August 2001
Michael Alekhnovich, Jan Johannsen, Alasdair Urquhart

An Exponential Separation between Regular and General Resolution

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.

more >>>



ISSN 1433-8092 | Imprint