Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-114 | 28th September 2007 00:00

A Simplified Way of Proving Trade-off Results for Resolution


Authors: Jakob Nordström
Publication: 15th November 2007 23:33
Downloads: 1152


We present a greatly simplified proof of the length-space
trade-off result for resolution in Hertel and Pitassi (2007), and
also prove a couple of other theorems in the same vein. We point
out two important ingredients needed for our proofs to work, and
discuss possible conclusions to be drawn regarding proving
trade-off results for resolution. Our key trick is to look at
formulas of the type F = G \land H, where G and H are over
disjoint set of variables and have very different length-space
properties with respect to resolution. This trick is not present
in the proof of Hertel and Pitassi, and thus their techniques can
likely be used to prove results not obtainable by our methods.

ISSN 1433-8092 | Imprint