# Special Monotone SAT problem: NP complete?

Say we have the set $$X=\{ x_1, x_2, \dots \}$$ of variables. Then we consider the following problem: Is the formula $$\bigwedge_{(a,b,c) \in A}(a \vee b \vee c) \wedge \bigwedge_{(a,b,c) \in B}(\neg a \vee \neg b \vee \neg c)$$ for $$A,B \subset X^3$$ satisfiable.

This problem has been called Montone-3-Sat before and it is known to be NP-complete.

My question is: If we assume that $$A=B$$ has to hold, is the problem still NP-complete? I.e. we ask if we can color vertices in such a way that always specific three of them do not have the same color.

The results I have found on the internet confuse me a bit, because I believe the definitions of Monotone-Sat, Not-All-Equal-Sat are not always the same. The definitions of NAE3SAT I've seen allow arbitrary 3-CNF-formulae as input, so this doesn't seem the same as that.

The variant where $$A=B$$ is known as monotone not-all-equal 3-satisfiability, i.e., Monotone NAE3SAT. According to Wikipedia, it is NP-complete. It is not the same problem as Monotone-3-SAT.
• Thank you very much. I think my confusion stems from the fact that it seems to me that some allow people allow arbitrary 3-CNF-formulae as input for NAE3SAT and then ask if for every clause, we can find values different from TTT and FFF. As a simple example, for my problem $x_1\vee \neg x_2 \vee x_3$ is not a valid input. For some other people it would be a valid input and the formula would be NAE3-satisfiable for them by assigning e.g. $x_{1,2,3} = T$, because then we have TFT for our clause which is different from TTT and FFF. – blablablup Feb 10 at 20:22
• Thank you! The definition of Monotone NAE3SAT for most people however seems to be the problem above with $B=\emptyset$. So they only allow non-negated literals. This would again be different from my problem. (see e.g. bit.ly/2UGjPQR) – blablablup Feb 11 at 9:18
• Perhaps I'm confused, but NAE3SAT with the clause $(x_1, x_2, x_3)$ seems equivalent to me to your problem with $A=B=\{(x_1,x_2,x_3)\}$. So your problem with $A=B$ seems equivalent to Monotone NAE3SAT to me. Your problem with $B=\emptyset$ seems to be equivalent to Monotone 3SAT, not Monotone NAE3SAT. Am I missing something again? – D.W. Feb 11 at 9:34