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.

Comments (1)


Linked Articles

Local articles referenced by this article:

References