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

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?

  • 1
    $\begingroup$ Why is $m=\Theta(n^k)$? That assumption is not correct, there are exponentially many possible CNFs with $n$ variables. $\endgroup$ – Kaveh Aug 10 '15 at 18:26
  • $\begingroup$ When talking about running time $n$ typically, and unless stated otherwise explicitly, represents the size of the input (not the number of variables). $\endgroup$ – Kaveh Aug 10 '15 at 18:28
  • 2
    $\begingroup$ I don't understand your argument. Just because you have shown that the algorithm is $O(n^k 2^n)$ does not mean that the algorithm cannot be $O(2^n)$. My understanding was that O is only the upper bound. A more clever complexity proof can prove better upper bound complexity results than your naive approach. $\endgroup$ – Tushar Aug 10 '15 at 22:12
  • 2
    $\begingroup$ What research have you done? Where have you looked? Where did you read that DPLL's running time is $O(2^n)$? What did they say to justify this? We expect you to do a significant amount of research before asking and to show us in the question what research you've done; this helps give you better answers, helps others who might run across your question, and incidentally sometimes enables you to solve your own problem yourself. $\endgroup$ – D.W. Aug 11 '15 at 6:35
  • 1
    $\begingroup$ Most likely, the bound on the running time should be understood as $\tilde{O}(2^n)$ rather than the strict $O(2^n)$. That is, we ignore polynomial factors. $\endgroup$ – Yuval Filmus Aug 11 '15 at 21:27

Your Answer

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

Browse other questions tagged or ask your own question.