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 21:55] 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 119: | Line 121: | ||
| This does not contradict P vs NP question, because there may be "better" proof systems than resolution. | This does not contradict P vs NP question, because there may be "better" proof systems than resolution. | ||
| - | Lower bounds for both resolution and a stronger system are shown here by proving that interpolants can be exponential, and that interpolants are polynomial in proof size: | + | Lower bounds for both resolution and a stronger system are shown here by proving that interpolants can be exponential, and that interpolants are polynomial in proof size (see [[Interpolants from Resolution Proofs]]): |
| * 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. | ||