Towards Understanding and Harnessing the Potential of Clause Learning

Details Towards Understanding and Harnessing the Potential of Clause Learning Towards Understanding and Harnessing the Potential of Clause Learning

2011-06-30

arxiv.org/abs/1107.0044v1

Journal Of Artificial Intelligence Research, Volume 22, pages 319-351, 2004

Computer Science

Artificial Intelligence

Scientific paper

10.1613/jair.1410

Efficient implementations of DPLL with the addition of clause learning are the fastest complete Boolean satisfiability solvers and can handle many significant real-world problems, such as verification, planning and design. Despite its importance, little is known of the ultimate strengths and limitations of the technique. This paper presents the first precise characterization of clause learning as a proof system (CL), and begins the task of understanding its power by relating it to the well-studied resolution proof system. In particular, we show that with a new learning scheme, CL can provide exponentially shorter proofs than many proper refinements of general resolution (RES) satisfying a natural property. These include regular and Davis-Putnam resolution, which are already known to be much stronger than ordinary DPLL. We also show that a slight variant of CL with unlimited restarts is as powerful as RES itself. Translating these analytical results to practice, however, presents a challenge because of the nondeterministic nature of clause learning algorithms. We propose a novel way of exploiting the underlying problem structure, in the form of a high level problem description such as a graph or PDDL specification, to guide clause learning algorithms toward faster solutions. We show that this leads to exponential speed-ups on grid and randomized pebbling problems, as well as substantial improvements on certain ordering formulas.

Affiliated with

Also associated with

No associations

Rating

Towards Understanding and Harnessing the Potential of Clause Learning does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Towards Understanding and Harnessing the Potential of Clause Learning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards Understanding and Harnessing the Potential of Clause Learning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-480012