Jan Johannsen: Lower bounds for width-restricted clause learning
Clause learning is a technique used by backtracking-based propositional satisfiability solvers, where some clauses obtained by an analysis of conflicts are added to the formula during backtracking. It has been observed empirically that clause learning does not significantly improve the performance of a solver when restricted to learning clauses of small width only. This experience is supported by several lower bound theorems.
abgelegt unter: Oberseminar