7
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\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$ Commented Nov 2, 2013 at 9:28
  • $\begingroup$ nice reduction! $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented Apr 28, 2022 at 14:28

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.