Definition
3-Horn Satisfiability Decision Problem
Instance: A Boolean formula
in conjunctive normal form, with at most three positive literals in each clause. Here “3-Horn” denotes this positive-literal bound; the number of negative literals is unrestricted. Question: Does there exist a truth assignment
such that Unlike 3-SAT, this restriction does not bound the total clause size. It relaxes the at-most-one-positive-literal condition of a Horn formula.