# Why is DPLL better than brute force?

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....)?

• 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.
– D.W.
Commented Nov 30, 2014 at 4:37
• 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. Commented Nov 30, 2014 at 22:30
• 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.
– vzn
Commented Dec 1, 2014 at 16:52