Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-164 | 25th October 2016 12:09

Relating two width measures for resolution proofs

RSS-Feed




TR16-164
Authors: Andreas Krebs, Meena Mahajan, Anil Shukla
Publication: 29th October 2016 12:33
Downloads: 520
Keywords: 


Abstract:

In this short note, we revisit two hardness measures for resolution proofs: width and asymmetric width. It is known that for every unsatisfiable CNF F,

width(F \derives \Box) \le awidth(F \derives \Box) + max{ awidth(F \derives \Box), width(F)}.

We give a simple direct proof of the upper bound, also shaving off a +1.



ISSN 1433-8092 | Imprint