# Computational Complexity of 'Generic'/'Relaxed' Horn 3SAT

Horn 3SAT are described as the 3SAT with at most one positive literal. And its in P. What about the complexity of relaxed case of 2-Horn 3SAT i.e.

Each clause is in CNF, has exactly 3 literals, with at most 2 positive literals.

Schaefer's dichotomy theorem gives you the answer. Apply it and see what you get, and let us know.

Looking at the modern formulation, in your case $\Gamma$ contains the three relations $\lnot x \lor \lnot y \lor \lnot z, x \lor \lnot y \lor \lnot z, x \lor y \lor \lnot z$. For each of these relations $R$, you have to go over the list of polymorphisms, and check whether one of them is a polymorphism of $R$. For example, to check whether the binary AND function is a polymorphism of $\lnot x \lor \lnot y \lor \lnot z$, you have to check whether $$(\lnot x_1 \lor \lnot y_1 \lor \lnot z_1) \land (\lnot x_2 \lor \lnot y_2 \lor \lnot z_2) \\ \Longrightarrow \lnot (x_1 \land x_2) \lor \lnot (y_1 \land y_2) \lor \lnot (z_1 \land z_2).$$ If every $R \in \Gamma$ has one of the six polymorphisms, then your problem is in P. Otherwise, it's NP-complete.

• first i would sincerely like to thank you (and people like you) who are here to help others even with the trivial of queries.. you guys are an asset beyond words.. :) In Schaefer's dichotomy theorem since every clause has a negative literal assigning a 'Complement/0' value to all variables in the problem would easily satisfy the 'Relaxed' Horn 3SAT. Hence its in P. Apr 20 '15 at 7:43