Question

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.

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top