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 19:31] vkuncak |
sav08:dpll_algorithm_for_sat [2008/03/13 17:45] vkuncak |
||
|---|---|---|---|
| Line 33: | Line 33: | ||
| <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 39: | Line 39: | ||
| val P = pick variable from FV(S') | val P = pick variable from FV(S') | ||
| DPLL(F' union {p}) or DPLL(F' union {Not(p)}) | DPLL(F' union {p}) or DPLL(F' union {Not(p)}) | ||
| + | </code> | ||
| + | |||
| + | <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> | </code> | ||
| Line 121: | Line 128: | ||
| 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]] | ||
| - | |||