2
$\begingroup$

A complete $k$-CNF formula is a $k$-CNF formula which contains all clauses of size $k$ or lower it implies.

Deciding the satisfiability of a $k$-CNF formula is clearly a tractable problem since a $k$-CNF formula is satisfiable as long as it does not contain the empty clause. What happens when it is mixed with a 2-CNF formula?

Let define the Complete (3,2) SAT problem : Given $F_3$, a complete 3-CNF formula, and $F_2$, a (complete) 2-CNF formula ($F_3$ and $F_2$ are defined on the same variables). Is $F_3 \wedge F_2$ satisfiable?

What is the complexity of this problem ?

(The question is different as in the post Complexity of the (3,2)s SAT problem? where it concerned non complete formulas.)

$\endgroup$
7
  • 1
    $\begingroup$ It does not matter whether $F_2$ is complete or not, as you can compute the completion of a 2-CNF in polynomial time. $\endgroup$ May 12 at 13:01
  • $\begingroup$ True, for $F_2$, it doesn't matter. $\endgroup$ May 12 at 13:52
  • $\begingroup$ What is "all the $k'$-clauses" with respect to $k$ ? $\endgroup$ May 13 at 9:08
  • $\begingroup$ @MarzioDeBiasi A $k'-$clause is a clause containing exactly $k'$ literals with $k'\le k$ : "all the $k'-$clause" means all clauses of size $k$ or lower that the $k-$CNF formula implies. $\endgroup$ May 13 at 9:57
  • $\begingroup$ @MarzioDeBiasi Tks for your comment, I edit the post to clarify the point. $\endgroup$ May 13 at 10:04

1 Answer 1

2
$\begingroup$

Consider the standard reduction from 3-coloring to SAT: for each vertex $v \in V$ we introduce three variables, $v_R,v_G,v_B$, add a clause $(v_R \vee v_G \vee v_B)$, and clauses $(\lnot v_R \vee \lnot v_G)$, $(\lnot v_R \vee \lnot v_B)$, and $(\lnot v_G \vee \lnot v_B)$. Then for each edge $(u,v) \in E$ we add clauses $(\lnot v_R \vee \lnot u_R)$, $(\lnot v_G \vee \lnot u_G)$, and $(\lnot v_B \vee \lnot v_B)$.

Observe that the clauses of size 3 in the resulting CNF are disjoint, and therefore the CNF consisting of them is complete. Therefore deciding the satisfiability of $F_3 \wedge F_2$, where $F_3$ is a complete 3-CNF formula and $F_2$ is a 2-CNF formula is an NP-complete problem.

$\endgroup$
1
  • $\begingroup$ Quite convincing, thank you ! $\endgroup$ May 16 at 19:31

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.