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.

  • $\begingroup$ 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. $\endgroup$
    – blablablup
    Feb 10 '20 at 20:22
  • $\begingroup$ @blablablup, you're right, I was confused. See my updated answer. $\endgroup$
    – D.W.
    Feb 10 '20 at 22:32
  • $\begingroup$ 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) $\endgroup$
    – blablablup
    Feb 11 '20 at 9:18
  • $\begingroup$ Another source with both (monotone) NAE3SAT mentioned: courses.csail.mit.edu/6.890/fall14/scribe/lec4.pdf $\endgroup$
    – blablablup
    Feb 11 '20 at 9:31
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Feb 11 '20 at 9:34

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.