Editing Boolean satisfiability problem (section)

===Horn-satisfiability===
{{Main|Horn-satisfiability}}

The problem of deciding the satisfiability of a given conjunction of [[Horn clause]]s is called '''Horn-satisfiability''', or '''HORN-SAT'''. It can be solved in polynomial time by a single step of the [[unit propagation]] algorithm, which produces the single minimal model of the set of Horn clauses (w.r.t. the set of literals assigned to TRUE). Horn-satisfiability is [[P-complete]]. It can be seen as [[P (complexity)|P's]] version of the Boolean satisfiability problem. Also, deciding the truth of quantified Horn formulas can be done in polynomial time.<ref name="buningkarpinski">{{Cite journal | last1 = Buning | first1 = H.K. | last2 = Karpinski| first2 =  Marek| last3=Flogel|first3=A.|year = 1995 | title = Resolution for Quantified Boolean Formulas | journal = Information and Computation | volume = 117 | issue = 1 | pages = 12–18 | publisher = Elsevier | doi= 10.1006/inco.1995.1025| doi-access = free }}</ref>

Horn clauses are of interest because they are able to express [[Entailment|implication]] of one variable from a set of other variables. Indeed, one such clause ¬''x''<sub>1</sub> ∨ ... ∨ ¬''x''<sub>''n''</sub> ∨ ''y'' can be rewritten as ''x''<sub>1</sub> ∧ ... ∧ ''x''<sub>''n''</sub> → ''y''; that is, if ''x''<sub>1</sub>,...,''x''<sub>''n''</sub> are all TRUE, then ''y'' must be TRUE as well.

A generalization of the class of Horn formulas is that of renameable-Horn formulae, which is the set of formulas that can be placed in Horn form by replacing some variables with their respective negation. For example, (''x''<sub>1</sub> ∨ ¬''x''<sub>2</sub>) ∧ (¬''x''<sub>1</sub> ∨ ''x''<sub>2</sub> ∨ ''x''<sub>3</sub>) ∧ ¬''x''<sub>1</sub> is not a Horn formula, but can be renamed to the Horn formula (''x''<sub>1</sub> ∨ ¬''x''<sub>2</sub>) ∧ (¬''x''<sub>1</sub> ∨ ''x''<sub>2</sub> ∨ ¬''y''<sub>3</sub>) ∧ ¬''x''<sub>1</sub> by introducing ''y''<sub>3</sub> as negation of ''x''<sub>3</sub>. In contrast, no renaming of (''x''<sub>1</sub> ∨ ¬''x''<sub>2</sub> ∨ ¬''x''<sub>3</sub>) ∧ (¬''x''<sub>1</sub> ∨ ''x''<sub>2</sub> ∨ ''x''<sub>3</sub>) ∧ ¬''x''<sub>1</sub> leads to a Horn formula. Checking the existence of such a replacement can be done in linear time; therefore, the satisfiability of such formulae is in P as it can be solved by first performing this replacement and then checking the satisfiability of the resulting Horn formula.

{| style="float:right"
| [[File:Boolean satisfiability vs true literal counts.png|thumb|x200px|A formula with 2 clauses may be unsatisfied (red), 3-satisfied (green), xor-3-satisfied (blue), or/and 1-in-3-satisfied (yellow), depending on the TRUE-literal count in the 1st (hor) and 2nd (vert) clause.]]
|}