Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
