[Solved]: Is the DPLL algorithm complexity in terms of # of clauses or # of variables?

Problem Detail: 

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?

Asked By : Rich

Answered By : Kyle Jones

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14004