# Complexity of the Complete (3,2) SAT problem?

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

• It does not matter whether $F_2$ is complete or not, as you can compute the completion of a 2-CNF in polynomial time. May 12, 2022 at 13:01
• True, for $F_2$, it doesn't matter. May 12, 2022 at 13:52
• What is "all the $k'$-clauses" with respect to $k$ ? May 13, 2022 at 9:08
• @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. May 13, 2022 at 9:57
• @MarzioDeBiasi Tks for your comment, I edit the post to clarify the point. May 13, 2022 at 10:04

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.