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$
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$
6
  • $\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$
    – Xavier Labouze
    Nov 2 '13 at 9:28
  • $\begingroup$ nice reduction! $\endgroup$
    – Vor
    Nov 2 '13 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 '13 at 17:23
  • $\begingroup$ @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. $\endgroup$
    – Xavier Labouze
    Nov 2 '13 at 23:13
  • $\begingroup$ 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.. ? $\endgroup$
    – TheoryQuest1
    May 16 '17 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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