Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RESOLUTION, CLAUSE LEARNING:
Reports tagged with resolution, clause learning:
TR13-072 | 3rd May 2013
Jan Johannsen

Exponential Separations in a Hierarchy of Clause Learning Proof Systems

Resolution trees with lemmas ($\mathrm{RTL}$) are a resolution-based propositional proof system that is related to the DPLL algorithm with clause learning. Its fragments $\mathrm{RTL}(k)$ are related to clause learning algorithms where the width of learned clauses is bounded by $k$.

For every $k$ up to $O(\log n)$, an exponential separation ... more >>>




ISSN 1433-8092 | Imprint