LARA

Differences

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

Link to this comparison view

Next revision
Previous revision
Next revision Both sides next revision
sav08:polynomial_algorithm_for_horn_clauses [2008/03/12 01:32]
vkuncak created
sav08:polynomial_algorithm_for_horn_clauses [2008/03/12 14:10]
vkuncak
Line 2: Line 2:
  
 A Horn clause is a clause that has at most one positive literal. 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 $\{\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.
  
 To check satisfiability of a set of Horn clauses: To check satisfiability of a set of Horn clauses:
-  ​* set initially all variables to false +  * while the set contains a clause of the form $\{p\}$ where $p$ is a propositional variable, do //boolean constraint propagation//​:
-  ​* while the set contains a clause of the form $\{p\}$ where $p$ is a propositional variable:+
      * erase all clauses that contain literal $p$       * 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 
 + 
 +Boolean constraint propagation is a sound inference rule.  If we obtain contradiction,​ the set is therefore unsatisfiable. 
 + 
 +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.