5
$\begingroup$

I understand that by being clever about the way we navigate the search space of the SAT problem we're going to get better performance than by randomly choosing and testing solutions, though of course both methods have $O(2^n)$ time complexity. What are the specific reasons that DPLL gives better performance than brute-force (sequentially testing solutions from FALSE-FALSE-FALSE.... to TRUE-TRUE-TRUE....)?

$\endgroup$
  • 1
    $\begingroup$ What research have you done? What resources have you read? There are lots of standard descriptions of DPLL (e.g., in textbooks), and in my experience they all explain why it is better than brute-force trying all possibilities (hint: pruning...) We expect you to do a significant amount of research/self-study before asking here, and to tell us in the question what you've tried. $\endgroup$ – D.W. Nov 30 '14 at 4:37
  • 1
    $\begingroup$ Worst-case complexity alone does not capture relevant properties of an algorithm. A brute force approach like constructing a truth table would require exponential time on all instances. Algorithms in the DPLL-family have polynomial runtime on 2SAT problems. One way to think of DPLL is decomposing an arbitrary SAT problem into efficiently solvable instances. Modern techniques control the size of the decomposition. $\endgroup$ – Vijay D Nov 30 '14 at 22:30
  • $\begingroup$ this shows some of the difference between empirical and theoretical/ abstract complexity. theoretically they have identical worse case complexity. on actual instances, on average, DPLL will "finish sooner". so "performance" empircally comes down to "how many (frequent?) worse case instances are in the test set". and some concept of this "difference" can be found in study of statistics. essentially, imagine different runtime profiles as different probability distributions. $\endgroup$ – vzn Dec 1 '14 at 16:52
7
$\begingroup$

Local (stochastic) search is all about clever navigation of the search space. DPLL's advantage is pruning the search space of large swaths of assignments that provably cannot satisfy the formula. DPLL does this by incrementally building partial assignments (some variables assigned values, some left unassigned), applying the unit propagation and pure literal rules and then checking if the resulting formula is trivially unsatisfiable. If the simplified formula implied by the partial assignment contains an empty clause, DPLL need not try assigning values to the remaining unassigned variables since the empty clause represents a clause that can never be satisfied under the partial assignment. The time saved is exponential to the number of unassigned variables, and those skipped assignments are where DPLL improves on brute force sequential search.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.