6 From Analysis to Practice

The complexity bounds established in the previous sections indicate that clause learning is potentially quite powerful, especially when compared to ordinary DPLL. However, natural choices such as which conflict graph to choose, which cut in it to consider, in what order to branch on variables, and when to restart, make the process highly nondeterministic. These choices must be made deterministically (or randomly) when implementing a clause learning algorithm. To harness its full potential on a given problem domain, one must, in particular, implement a learning scheme and a branch decision process suited to that domain.



Subsections
Journal of Artificial Intelligence Research 22 (2004). Copyright AI Access Foundation. All rights reserved.