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.

Can someone please help with the reference.


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.

  • $\begingroup$ 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. $\endgroup$ Apr 20 '15 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.