Editing Horn-satisfiability

In [[formal logic]], '''Horn-satisfiability''', or '''HORNSAT''', is the [[Decision problem|problem]] of deciding whether a given conjunction of propositional [[Horn clause]]s is [[Boolean satisfiability|satisfiable]] or not. Horn-satisfiability and Horn clauses are named after [[Alfred Horn]].<ref name="Horn51">{{cite journal |last1=Horn |first1=Alfred |title=On sentences which are true of direct unions of algebras |journal=Journal of Symbolic Logic |date=March 1951 |volume=16 |issue=1 |pages=14–21 |doi=10.2307/2268661}}</ref>

A Horn clause is a [[Clause (logic)|clause]] with at most one positive [[literal (mathematical logic)|literal]], called the ''head'' of the clause, and any number of negative literals, forming the ''body'' of the clause. A Horn formula is a [[propositional formula]] formed by [[logical and|conjunction]] of Horn clauses.

Horn satisfiability is actually one of the "hardest" or "most expressive" problems which is known to be computable in polynomial time, in the sense that it is a [[P-complete|'''P'''-complete]] problem.<ref name="CookNguyen2010">{{cite book|author1=Stephen Cook|author2=Phuong Nguyen|title=Logical foundations of proof complexity|url=https://books.google.com/books?id=2aW2sSlQj_QC&pg=PA224|year=2010|publisher=Cambridge University Press|isbn=978-0-521-51729-4|page=224}} ([https://www.cs.toronto.edu/~sacook/homepage/book Author's 2008 draft version], see p.213f)</ref> The extension of the problem for [[Quantified Boolean formula|quantified]] Horn formulae can be also solved 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>

The Horn satisfiability problem can also be asked for propositional [[many-valued logic]]s. The algorithms are not usually linear, but some are polynomial; see Hähnle (2001 or 2003) for a survey.<ref>{{cite book|editor=Dov M. Gabbay, Franz Günthner|title=Handbook of philosophical logic|chapter-url=https://books.google.com/books?id=_ol81ow-1s4C&pg=PA373|year=2001|publisher=Springer|isbn=978-0-7923-7126-7|page=373|chapter=Advanced many-valued logics|author=Reiner Hähnle|edition=2nd|volume=2}}</ref><ref name="FittingOrlowska2003">{{cite book|editor=Melvin Fitting, [[Ewa Orłowska]]|title=Beyond two: theory and applications of multiple-valued logic|year=2003|publisher=Springer|isbn=978-3-7908-1541-2|author=Reiner Hähnle|chapter=Complexity of Many-valued Logics}}</ref>

==Algorithm==

The problem of Horn satisfiability is solvable in [[linear time]].<ref>{{citation
 | last1 = Dowling | first1 = William F.
 | last2 = Gallier | first2 = Jean H. | author2-link = Jean Gallier
 | doi = 10.1016/0743-1066(84)90014-1
 | issue = 3
 | journal = Journal of Logic Programming
 | mr = 770156
 | pages = 267–284
 | title = Linear-time algorithms for testing the satisfiability of propositional Horn formulae
 | volume = 1
 | year = 1984| doi-access = free
 }}</ref> 
A polynomial-time algorithm for Horn satisfiability is [[Recursion (computer science)|recursive]]:
* A first termination condition is a formula in which all the clauses currently existing contain negative literals. In this case, all the variables currently in the clauses can be set to false.
* A second termination condition is an empty clause. In this case, the formula has no solutions.
* In the other cases, the formula contains a positive unit clause <math>l</math>, so we do a [[unit propagation]]: the literal <math>l</math> is set to true, all the clauses containing <math>l</math> are removed, and all clauses containing <math>\neg l</math> have this literal removed. The result is a new Horn formula, so we reiterate.

This algorithm also allows determining a truth assignment of satisfiable Horn formulae: all variables contained in a unit clause are set to the value satisfying that unit clause; all other literals are set to false. The resulting assignment is the minimal model of the Horn formula, that is, the assignment having a minimal set of variables assigned to true, where comparison is made using set containment.

Using a linear algorithm for unit propagation, the algorithm is linear in the size of the formula.

===Examples===
====Trivial case====
In the Horn formula
:{{math|(¬''a''&nbsp;∨&nbsp;¬''b''&nbsp;∨&nbsp;''c'')&nbsp;∧}}
:{{math|(¬''b''&nbsp;∨&nbsp;¬''c''&nbsp;∨&nbsp;''d'')&nbsp;∧}}
:{{math|(¬''f''&nbsp;∨&nbsp;¬''a''&nbsp;∨&nbsp;''b'')&nbsp;∧}}
:{{math|(¬''e''&nbsp;∨&nbsp;¬''c''&nbsp;∨&nbsp;''a'')&nbsp;∧}}
:{{math|(¬''e''&nbsp;∨&nbsp;''f'')&nbsp;∧}}
:{{math|(¬''d''&nbsp;∨&nbsp;''e'')&nbsp;∧}}
:{{math|(¬''b''&nbsp;∨&nbsp;¬''c'')}},

each clause has a negated literal. Therefore, setting each variable to false satisfies all clauses, hence it is a solution.

====Solvable case====
In the Horn formula
:{{math|(¬''a''&nbsp;∨&nbsp;¬''b''&nbsp;∨&nbsp;''c'')&nbsp;∧}}
:{{math|(¬''b''&nbsp;∨&nbsp;¬''c''&nbsp;∨&nbsp;''f'')&nbsp;∧}}
:{{math|(¬''f''&nbsp;∨&nbsp;''b'')&nbsp;∧}}
:{{math|(¬''e''&nbsp;∨&nbsp;¬''c''&nbsp;∨&nbsp;''a'')&nbsp;∧}}
:{{math|(''f'')&nbsp;∧}}
:{{math|(¬''d''&nbsp;∨&nbsp;''e'')&nbsp;∧}}
:{{math|(¬''b''&nbsp;∨&nbsp;¬''c'')}},

one clause forces ''f'' to be true. Setting ''f'' to true and simplifying gives
:{{math|(¬''a''&nbsp;∨&nbsp;¬''b''&nbsp;∨&nbsp;''c'')&nbsp;∧}}
:{{math|(''b'')&nbsp;∧}}
:{{math|(¬''e''&nbsp;∨&nbsp;¬''c''&nbsp;∨&nbsp;''a'')&nbsp;∧}}
:{{math|(¬''d''&nbsp;∨&nbsp;''e'')&nbsp;∧}}
:{{math|(¬''b''&nbsp;∨&nbsp;¬''c'')}}.

Now ''b'' must be true.  Simplification gives
:{{math|(¬''a''&nbsp;∨&nbsp;''c'')&nbsp;∧}}
:{{math|(¬''e''&nbsp;∨&nbsp;¬''c''&nbsp;∨&nbsp;''a'')&nbsp;∧}}
:{{math|(¬''d''&nbsp;∨&nbsp;''e'')&nbsp;∧}}
:{{math|(¬''c'')}}.

Now it is a trivial case, so the remaining variables can all be set to false. Thus, a satisfying assignment is
:{{math|1=''a''&nbsp;=&nbsp;false}},
:{{math|1=''b''&nbsp;=&nbsp;true}},
:{{math|1=''c''&nbsp;=&nbsp;false}},
:{{math|1=''d''&nbsp;=&nbsp;false}},
:{{math|1=''e''&nbsp;=&nbsp;false}},
:{{math|1=''f''&nbsp;=&nbsp;true}}.

====Unsolvable case====
In the Horn formula
:{{math|(¬''a''&nbsp;∨&nbsp;¬''b''&nbsp;∨&nbsp;''c'')&nbsp;∧}}
:{{math|(¬''b''&nbsp;∨&nbsp;¬''c''&nbsp;∨&nbsp;''f'')&nbsp;∧}}
:{{math|(¬''f''&nbsp;∨&nbsp;''b'')&nbsp;∧}}
:{{math|(¬''e''&nbsp;∨&nbsp;¬''c''&nbsp;∨&nbsp;''a'')&nbsp;∧}}
:{{math|(''f'')&nbsp;∧}}
:{{math|(¬''d''&nbsp;∨&nbsp;''e'')&nbsp;∧}}
:{{math|(¬''b'')}},

one clause forces ''f'' to be true.  Subsequent simplification gives
:{{math|(¬''a''&nbsp;∨&nbsp;¬''b''&nbsp;∨&nbsp;''c'')&nbsp;∧}}
:{{math|(''b'')&nbsp;∧}}
:{{math|(¬''e''&nbsp;∨&nbsp;¬''c''&nbsp;∨&nbsp;''a'')&nbsp;∧}}
:{{math|(¬''d''&nbsp;∨&nbsp;''e'')&nbsp;∧}}
:{{math|(¬''b'')}}.

Now ''b'' has to be true. Simplification gives
:{{math|(¬''a''&nbsp;∨&nbsp;''c'')&nbsp;∧}}
:{{math|(¬''e''&nbsp;∨&nbsp;¬''c''&nbsp;∨&nbsp;''a'')&nbsp;∧}}
:{{math|(¬''d''&nbsp;∨&nbsp;''e'')&nbsp;∧}}
:{{math|()}}.
We obtained an empty clause, hence the formula is unsatisfiable.

==Generalization==

A generalization of the class of Horn formulae is that of renamable-Horn formulae, which is the set of formulae that can be placed in Horn form by replacing some variables with their respective negation. 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.<ref>{{cite journal
 | last = Lewis | first = Harry R. | author-link = Harry R. Lewis
 | doi = 10.1145/322047.322059
 | issue = 1
 | journal = [[Journal of the ACM]]
 | mr = 0468315
 | pages = 134–135
 | title = Renaming a set of clauses as a Horn set
 | volume = 25
 | year = 1978| doi-access = free
 }}.</ref><ref>{{cite journal
 | last = Aspvall | first = Bengt
 | doi = 10.1016/0196-6774(80)90007-3
 | issue = 1
 | journal = Journal of Algorithms
 | mr = 578079
 | pages = 97–103
 | title = Recognizing disguised NR(1) instances of the satisfiability problem
 | volume = 1
 | year = 1980}}</ref><ref>{{cite journal
 | last = Hébrard | first = Jean-Jacques
 | doi = 10.1016/0304-3975(94)90015-9
 | issue = 2
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 1260003
 | pages = 343–350
 | title = A linear algorithm for renaming a set of clauses as a Horn set
 | volume = 124
 | year = 1994| doi-access = 
 }}.</ref><ref>
{{cite journal
| last=Chandru
| first=Vijaya
|author2=Collette R. Coullard|author2-link=Collette Coullard |author3=Peter L. Hammer |author4=Miguel Montañez |author5=Xiaorong Sun
 | title=On renamable Horn and generalized Horn functions
| journal=Annals of Mathematics and Artificial Intelligence
| year=2005
| doi=10.1007/BF01531069
| volume=1
| issue=1–4
| pages=33–47
}}</ref> Horn satisfiability and renamable Horn satisfiability provide one of two important subclasses of satisfiability that are solvable in polynomial time; the other such subclass is [[2-satisfiability]].

===Dual-Horn SAT===

A dual variant of Horn SAT is '''Dual-Horn SAT''', in which each clause has at most one negative literal. Negating all variables transforms an instance of Dual-Horn SAT into Horn SAT. It was proven in 1951 by Horn that Dual-Horn SAT is in [[P_(complexity)|P]]. {{Citation needed|reason=where is the paper|date=November 2022}}

==See also==

* [[Unit propagation]]
* [[Boolean satisfiability problem]]
* [[2-satisfiability]]

==References==
<references />

==Further reading==
* {{cite book | last1=Grädel | first1=Erich | last2=Kolaitis | first2=Phokion G. | last3=Libkin | first3=Leonid | last4=Maarten | first4=Marx | last5=Spencer | first5=Joel | author5-link=Joel Spencer | last6=Vardi | first6=Moshe Y. | author6-link=Moshe Y. Vardi | last7=Venema | first7=Yde | last8=Weinstein | first8=Scott | title=Finite model theory and its applications | zbl=1133.03001 | series=Texts in Theoretical Computer Science. An EATCS Series | location=Berlin | publisher=[[Springer-Verlag]] | isbn=978-3-540-00428-8 | year=2007 }}

[[Category:Logic in computer science]]
[[Category:P-complete problems]]
[[Category:Satisfiability problems]]