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:polynomial_algorithm_for_horn_clauses [2008/03/12 01:40] vkuncak |
sav08:polynomial_algorithm_for_horn_clauses [2008/03/12 01:41] vkuncak |
||
|---|---|---|---|
| Line 16: | Line 16: | ||
| On $\{p\}$ we conclude that $p$ must be true and derive valid consequences of this fact. If we obtain contradiction, the set of clearly unsatisfiable. | On $\{p\}$ we conclude that $p$ must be true and derive valid consequences of this fact. If we obtain contradiction, the set of clearly unsatisfiable. | ||
| - | Moreover, if loop terminates then every clause contains a negative literal. The assignment that sets all remaining variables to //false// is a satisfying assignment. | + | Moreover, if loop terminates and there are no empty clauses, then every clause contains a negative literal. The assignment that sets all remaining variables to //false// is a satisfying assignment. |
| + | This algorithm does polynomial amount of work for each propositional variable, so it is polynomial. | ||
| + | |||
| + | Conclusion: the difficulty are clauses with at least two positive literals, they require case analysis. | ||