Theoretical Computer Science
cc.complexity-theory np-hardness complexity-classes sat
Updated Fri, 20 May 2022 18:00:04 GMT

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

## Solution

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.