# Differences

This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision | ||

sav08:dpll_algorithm_for_sat [2013/04/17 17:34] vkuncak |
sav08:dpll_algorithm_for_sat [2015/04/21 17:30] (current) |
||
---|---|---|---|

Line 90: | Line 90: | ||

**Decision step** (picking variable value): from proofs for | **Decision step** (picking variable value): from proofs for | ||

- | \[ | + | \begin{equation*} |

S' \cup \{p\} \vdash {\it false} | S' \cup \{p\} \vdash {\it false} | ||

- | \] | + | \end{equation*} |

- | \[ | + | \begin{equation*} |

S' \cup \{\lnot p\} \vdash {\it false} | S' \cup \{\lnot p\} \vdash {\it false} | ||

- | \] | + | \end{equation*} |

we would like to construct the proof for | we would like to construct the proof for | ||

- | \[ | + | \begin{equation*} |

S' \vdash {\it false} | S' \vdash {\it false} | ||

- | \] | + | \end{equation*} |

From | From | ||

- | \[ | + | \begin{equation*} |

S' \cup \{p\} \vdash {\it false} | S' \cup \{p\} \vdash {\it false} | ||

- | \] | + | \end{equation*} |

derive proof tree for | derive proof tree for | ||

- | \[ | + | \begin{equation*} |

S' \vdash \lnot p | S' \vdash \lnot p | ||

- | \] | + | \end{equation*} |

and from | and from | ||

- | \[ | + | \begin{equation*} |

S' \cup \{\lnot p\} \vdash {\it false} | S' \cup \{\lnot p\} \vdash {\it false} | ||

- | \] | + | \end{equation*} |

derive proof tree for | derive proof tree for | ||

- | \[ | + | \begin{equation*} |

S' \vdash p | S' \vdash p | ||

- | \] | + | \end{equation*} |

Then combine these two trees with resolution on $\{p\}$ and $\{\lnot p\}$ to get ${\it false}$. | Then combine these two trees with resolution on $\{p\}$ and $\{\lnot p\}$ to get ${\it false}$. | ||

Line 127: | Line 127: | ||

Theorem: for some formulas, 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 that P vs NP question is open, 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 (see [[Interpolants from Resolution Proofs]]): | 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]] |