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 complete $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.)

  • 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$ Commented May 12, 2022 at 13:01
  • $\begingroup$ True, for $F_2$, it doesn't matter. $\endgroup$ Commented May 12, 2022 at 13:52
  • $\begingroup$ What is "all the $k'$-clauses" with respect to $k$ ? $\endgroup$ Commented May 13, 2022 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$ Commented May 13, 2022 at 9:57
  • $\begingroup$ @MarzioDeBiasi Tks for your comment, I edit the post to clarify the point. $\endgroup$ Commented May 13, 2022 at 10:04

1 Answer 1


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.

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

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.