# Complexity of Monotone (+,2) SAT problem?

To continue this post, let us define the Monotone$(+, 2^-)$-SAT problem:

Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF formula $F_2^-$ defined on the same variables as $F^+$, where all variables are negated. Is $F^+ \land F_2^-$ satisfiable ?

Is this problem NP-complete?

This is NP-complete. In fact, it remains NP-complete when $F^+$ is restricted to be in 3-CNF form (not just CNF).

The proof is by demonstrating that this problem is at least as hard as testing 3-colorability of a graph. The correspondence is clean and elegant. Let $G=(V,E)$ be an undirected graph. Introduce variables $x_{v,c}$, for $v \in V$ and $c \in \{1,2,3\}$, to represent a 3-coloring of the graph. Here $x_{v,c}$ means that we've given vertex $v$ the color $c$.

To represent that each vertex must receive at least one color, we will introduce clauses $x_{v,1} \lor x_{v,2} \lor x_{v,3}$ for each vertex $v$. This gives us $F^+$, i.e.,

$$F^+ \equiv \bigwedge_{v \in V} (x_{v,1} \lor x_{v,2} \lor x_{v,3}).$$

To represent that no two endpoints of a single edge may receive the same color, we will introduce a clause $\neg x_{u,c} \lor \neg x_{v,c}$ for each edge $(u,v) \in E$. And, to represent that no vertex may receive more than one color, we will introduce a clause $\neg x_{v,c} \lor \neg x_{v,c'}$ for each $c,c' \in \{1,2,3\}$ such that $c\ne c'.$ Let $F^-_2$ denote the corresponding formula.

$$F^-_2 \equiv \bigwedge_{(u,v) \in E} (\neg x_{u,c} \lor \neg x_{v,c}) \; \; \land \bigwedge_{v \in V,c\ne c'} (\neg x_{v,c} \lor \neg x_{v,c'}).$$

Then it is easy to see that $F^+ \land F^-_2$ is satisfiable if and only if $G$ has a 3-coloring. In fact, each satisfying assignment of $F^+ \land F^-_2$ corresponds immediately to a 3-coloring of $G$, and vice versa. Therefore, testing the satisfiability of this class of formulae is at least as hard as testing 3-colorability of an undirected graph, so it is NP-hard.

• Your correspondence with 3-colorability is clear indeed. Hence Monotone $(3^+,2^-)$ SAT Problem is clearly NP-complete. Nevertheless, it is still not clear (for me) that any CNF Monotone formula can be equivalent to a 3-CNF Monotone formula. – Xavier Labouze Nov 2 '13 at 9:28
• nice reduction! – Vor Nov 2 '13 at 10:55
• @XavierLabouze, sorry, you lost me. I didn't claim that every CNF Monotone formula is equivalent to a 3-CNF Monotone formula, and that's not needed at any step in my reduction. I do use the fact that any 3-CNF formula is also a CNF formula (this is trivial), from which it follows that the problem in the original post is also NP-complete. – D.W. Nov 2 '13 at 17:23
• @D.W. Right. I meant the reduction from $(+,2^-)$ SAT to $(3^+,2^-)$ SAT is not as clear as the one from SAT to 3-SAT. – Xavier Labouze Nov 2 '13 at 23:13
• I was searching for a smallest possible explicit example for $(3^+, 2^-)$ SAT that is unsatisfiable and verifiable by hand. I would be really grateful if you could help me with one.. ? – TheoryQuest1 May 16 '17 at 15:04