4
$\begingroup$

I'm a bit confused how worst case complexity is estimated for the DPLL algorithm. Is it in terms of number of clauses, number of variables, or something else?

$\endgroup$
7
  • 3
    $\begingroup$ It could also be in terms of the input length. Do you have any specific analysis in mind? Usually they explain what their variables mean. $\endgroup$ Aug 28 '13 at 21:07
  • $\begingroup$ http://en.wikipedia.org/wiki/DPLL_algorithm Worst case complexity says it's O(e^n). $\endgroup$
    – Rich
    Aug 28 '13 at 21:09
  • 2
    $\begingroup$ Here $n$ is probably input length. But don't trust Wikipedia - find an actual source. I see that Wikipedia doesn't quote any, so there's no reason to believe it. In particular, I suspect that by $O(e^n)$, they really mean $O(c^n)$ for some constant $c > 1$. $\endgroup$ Aug 28 '13 at 21:19
  • $\begingroup$ Input length being the number of clauses? Or the number of vairables. The DPLL is used to solve k-SAT, which is known to be NP-complete. However, I don't understand if it is NP-complete based on the number of variables or the number of clauses. $\endgroup$
    – Rich
    Aug 29 '13 at 23:14
  • $\begingroup$ Input length being the length of the input as a string. Roughly the total number of literals appearing in all the clauses. $\endgroup$ Aug 30 '13 at 22:11
4
$\begingroup$

In the papers I've read the time complexity of DPLL is expressed in terms of the number of variables in the CNF formula. Using the number of clauses is inappropriate in general because it is known that random k-SAT instances go through an easy-hard-easy transition if you fix the number of variables and increase the number of clauses. The solution space goes from underconstrained to overconstrained as the number of clauses increases with the hard instances clustering between those extremes.

$\endgroup$
1
  • $\begingroup$ Just to clarify what we mean by "number of variables": In a formula, we could have n variables, c clauses, and k literals per clause where a literal could be one of n unique variables with a truth value of True or False. $\endgroup$
    – Rich
    Aug 31 '13 at 2:27

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.