DPLL time complexity analysis - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T15:00:02Z https://cs.stackexchange.com/feeds/question/45144 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/45144 2 DPLL time complexity analysis matheuscscp https://cs.stackexchange.com/users/33810 2015-08-10T15:16:08Z 2018-04-02T10:19:20Z <p>Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $\phi$ when all the $n$ variables have values assigned. Let $m$ be the size of $\phi$. Then the time complexity for this backtracking is $O(m 2^n)$.</p> <p>Now, consider DPLL. This algorithm is just a simple backtracking with some pruning strategy. Besides, DPLL simplifies $\phi$ along the backtracking, instead of doing it only at once, so the $O(m)$ cost is amortized. Hence, its running time should also be $O(m 2^n)$. Still, some places state that $O(2^n)$ is also an upper bound for DPLL (Wikipedia, for example). Does anybody knows the analysis to find this upper bound?</p>