Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | Next revision Both sides next revision | ||
sav08:dpll_algorithm_for_sat [2008/03/12 18:25] vkuncak |
sav08:dpll_algorithm_for_sat [2008/03/12 18:28] vkuncak |
||
---|---|---|---|
Line 113: | Line 113: | ||
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. | ||
- | Theorem: for some formulas, the shortest resolution proofs are exponential. | + | Theorem: for some formulas, shortest resolution proofs are exponential. |
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: | ||
+ | * Pavel Pudlák: [[http://citeseer.ist.psu.edu/36219.html|Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations]] | ||
===== DPLL Imperatively ===== | ===== DPLL Imperatively ===== |