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 [2008/03/12 19:31] vkuncak |
sav08:dpll_algorithm_for_sat [2015/04/21 17:30] (current) |
||
---|---|---|---|
Line 28: | Line 28: | ||
Note: for each unit clause and other clause we can perform unit resolution at most once (variable disappears) | Note: for each unit clause and other clause we can perform unit resolution at most once (variable disappears) | ||
* BCP is polynomial procedure | * BCP is polynomial procedure | ||
+ | |||
+ | We do not need to keep literals that are subset of existing ones: | ||
+ | <code> | ||
+ | def RemoveSubsumed(S : Set[Clause]) : Set[Clause] = | ||
+ | if there are C1,C2 in S such that C1 subset C2 | ||
+ | then RemoveSubsumes(S - {C2}) | ||
+ | else S | ||
+ | </code> | ||
+ | In particular, when we apply unit resolution, the original clause can be deleted. | ||
===== DPLL Recursively ===== | ===== DPLL Recursively ===== | ||
Line 33: | Line 42: | ||
<code> | <code> | ||
def DPLL(S : Set[Clause]) : boolean = | def DPLL(S : Set[Clause]) : boolean = | ||
- | val S' = BCP(S) | + | val S' = RemoveSubsumed(BCP(S)) |
if (emptyClause in S') then false | if (emptyClause in S') then false | ||
else if (S' has only unit clauses) then true | else if (S' has only unit clauses) then true | ||
Line 81: | 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*} |
- | ++++Idea:| | + | |
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}$. | ||
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 === | === Lower Bounds on Running Time === | ||
Line 119: | 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: | + | 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]] | ||
- |