Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-085 | 20th May 2010 11:50

Lower bounds for width-restricted clause learning on small width formulas

RSS-Feed




TR10-085
Authors: Eli Ben-Sasson, Jan Johannsen
Publication: 20th May 2010 11:50
Downloads: 3421
Keywords: 


Abstract:

It has been observed empirically that clause learning does not significantly improve the performance of a SAT solver when restricted
to learning clauses of small width only. This experience is supported by lower bound theorems. It is shown that lower bounds on the runtime of width-restricted clause learning follow from resolution width lower bounds. This yields the first lower bounds on width-restricted clause learning for formulas in 3-CNF.



ISSN 1433-8092 | Imprint