Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav08:dpll_algorithm_for_sat [2008/03/12 18:34] vkuncak |
sav08:dpll_algorithm_for_sat [2008/03/12 19:31] vkuncak |
||
---|---|---|---|
Line 112: | Line 112: | ||
Why can we modify resolution proof to move $p$ from assumption and put its negation to conclusion? | Why can we modify resolution proof to move $p$ from assumption and put its negation to conclusion? | ||
++++ | ++++ | ||
+ | |||
+ | === Lower Bounds on Running Time === | ||
Observation: constructed resolution proof is polynomial in the running time of the DPLL algorithm. | Observation: constructed resolution proof is polynomial in the running time of the DPLL algorithm. | ||
Line 122: | Line 124: | ||
* Pavel Pudlák: [[http://citeseer.ist.psu.edu/36219.html|Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations]] | * Pavel Pudlák: [[http://citeseer.ist.psu.edu/36219.html|Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations]] | ||
- | ===== DPLL Imperatively ===== | ||
- | |||
- | |||
- | Selecting order of variables. | ||
- | |||
- | Lemma learning. |