Differences

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

--- sav08:polynomial_algorithm_for_horn_clauses [2008/03/12 01:40]
vkuncak
+++ sav08:polynomial_algorithm_for_horn_clauses [2008/03/12 15:59]
vkuncak
@@ Line 1: / Line 1: @@
-====== Polynomial Algorithm for Horn Clauses ======
+====== Boolean Constraint Propagation and Polynomial Algorithm for Horn Clauses ======
 A Horn clause is a clause that has at most one positive literal.
-Such clause is either of the form $\{p\}$ where $p \in V$ is a variable, or of the form $\{\lnot p_1, \ldots, \lnot p_n, q$ for $n \ge 1$, that is $p_1 \land \ldots \land p_n \rightarrow q$.
+Such clause is either of the form $\{p\}$ where $p \in V$ is a variable, or $\{\lnot p\}$ for $p \in V$, or of the form $\{\lnot p_1, \ldots, \lnot p_n, q\}$ for $n \ge 1$, that is $p_1 \land \ldots \land p_n \rightarrow q$.
-The following algorithm eliminates clauses of the form $\{p\}$, keeping only clauses that have at least one assumption.
+The following algorithm eliminates clauses of the form $\{p\}$, keeping only clauses that have at least one negative literal.
 To check satisfiability of a set of Horn clauses:
-  * while the set contains a clause of the form $\{p\}$ where $p$ is a propositional variable:
+  * while the set contains a clause of the form $\{p\}$ where $p$ is a propositional variable, do //boolean constraint propagation//:
      * erase all clauses that contain literal $p$
-     * remove $\lnot p$ from all literals
+     * remove $\lnot p$ from all clauses
-     * if there is an empty clause, set is not satisfiable
+     * if there is an empty clause, the set is unsatisfiable
-  * if no contradiction found, the set is satisfiable
+  * if no empty clause found after repeating the above, the set is satisfiable
-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.
+Boolean constraint propagation is a sound inference rule.  If we obtain contradiction, the set is therefore 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.
+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.