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?


1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$ Nov 2, 2013 at 9:28
  • $\begingroup$ nice reduction! $\endgroup$
    – Vor
    Nov 2, 2013 at 10:55
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Nov 2, 2013 at 17:23
  • 2
    $\begingroup$ I think that reduction from positive 1-in-3 clause $(x\lor y\lor z)$ to a set of clauses $(x\lor y\lor z)\land(\overline x\lor\overline y)\land(\overline x\lor\overline z)\land(\overline y\lor\overline z)$ would be much simplier answer. $\endgroup$
    – rus9384
    Aug 17, 2017 at 16:12
  • 2
    $\begingroup$ @rus9384 Indeed the reduction from positive 1-in-3 SAT appears to be more direct. Although it is worth pointing that the 3-COLORING reduction has the remarkable feat that each variable occurs exactly once positively, which could be useful. $\endgroup$ Apr 28, 2022 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.