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?
Complexity of Monotone (+,2) SAT problem?
complexity theory;np complete;decision problem;complexity classes
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.