6 Add 'time-complexity' tag
| link
5 added 40 characters in body
source | link

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)$. Then why everybody saysStill, some places state that DPLL running time is $O(2^n)$? I really can't see how the hell is also an upper bound for DPLL $m 2^n = \Theta(2^n)$(Wikipedia, for example). Does anybody knows the analysis to find this upper bound?

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)$. Then why everybody says that DPLL running time is $O(2^n)$? I really can't see how the hell $m 2^n = \Theta(2^n)$.

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?

4 deleted 203 characters in body
source | link

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)$. But we know that $m$ is a polynomial in $n$, so $m = \Theta(n^k)$ and the algorithm runs in $O(n^k 2^n)$, for some $k \geq 1$.

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(n^k)$$O(m)$ cost is amortized. Hence, its running time should also be $O(n^k 2^n)$$O(m 2^n)$. Then why everybody says that DPLL running time is $O(2^n)$? I really can't see how the hell $n^k 2^n = \Theta(2^n)$. Is easy to see that $\lim_{n\to\infty} \frac{n^k 2^n}{2^n} = \infty$$m 2^n = \Theta(2^n)$.

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)$. But we know that $m$ is a polynomial in $n$, so $m = \Theta(n^k)$ and the algorithm runs in $O(n^k 2^n)$, for some $k \geq 1$.

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(n^k)$ cost is amortized. Hence, its running time should also be $O(n^k 2^n)$. Then why everybody says that DPLL running time is $O(2^n)$? I really can't see how the hell $n^k 2^n = \Theta(2^n)$. Is easy to see that $\lim_{n\to\infty} \frac{n^k 2^n}{2^n} = \infty$.

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)$. Then why everybody says that DPLL running time is $O(2^n)$? I really can't see how the hell $m 2^n = \Theta(2^n)$.

3 fixed a typo; k -> n
source | link
2 edited tags
| link
1
source | link