<p>Consider the standard reduction from 3-coloring to SAT: for each vertex <span class="math-container">$v \in V$</span> we introduce three variables, <span class="math-container">$v_R,v_G,v_B$</span>, add a clause <span class="math-container">$(v_R \vee v_G \vee v_B)$</span>, and clauses <span class="math-container">$(\lnot v_R \vee \lnot v_G)$</span>, <span class="math-container">$(\lnot v_R \vee \lnot v_B)$</span>, and <span class="math-container">$(\lnot v_G \vee \lnot v_B)$</span>. Then for each edge <span class="math-container">$(u,v) \in E$</span> we add clauses <span class="math-container">$(\lnot v_R \vee \lnot u_R)$</span>, <span class="math-container">$(\lnot v_G \vee \lnot u_G)$</span>, and <span class="math-container">$(\lnot v_B \vee \lnot v_B)$</span>.</p>
<p>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 <span class="math-container">$F_3 \wedge F_2$</span>, where <span class="math-container">$F_3$</span> is a complete 3-CNF formula and <span class="math-container">$F_2$</span> is a 2-CNF formula is an NP-complete problem.</p>

CC BY-SA 4.0
2022-05-16T19:31:48.977Z
Quite convincing, thank you !
Xavier Labouze
CC BY-SA 4.0
2022-05-16T19:04:09.523Z
2022-05-16T19:04:09.523Z
Laakeri
<p>A complete <span class="math-container">$k$</span>-CNF formula is a <span class="math-container">$k$</span>-CNF formula which contains all clauses of size <span class="math-container">$k$</span> or lower it implies.</p>
<p>Deciding the satisfiability of a complete <span class="math-container">$k$</span>-CNF formula is clearly a tractable problem since a <span class="math-container">$k$</span>-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?</p>
<p>Let define the Complete (3,2) SAT problem : Given <span class="math-container">$F_3$</span>, a complete 3-CNF formula, and <span class="math-container">$F_2$</span>, a (complete) 2-CNF formula (<span class="math-container">$F_3$</span> and <span class="math-container">$F_2$</span> are defined on the same variables). Is <span class="math-container">$F_3 \wedge F_2$</span> satisfiable?</p>
<p>What is the complexity of this problem ?</p>
<p>(The question is different as in the post <a href="https://cstheory.stackexchange.com/questions/18379/complexity-of-the-3-2-s-sat-problem">Complexity of the (3,2)s SAT problem?</a> where it concerned non complete formulas.)</p>

CC BY-SA 4.0
2022-05-12T13:01:44.420Z
It does not matter whether $F_2$ is complete or not, as you can compute the completion of a 2-CNF in polynomial time.
Emil Jeřábek
CC BY-SA 4.0
2022-05-12T13:52:06.627Z
True, for $F_2$, it doesn't matter.
Xavier Labouze
CC BY-SA 4.0
2022-05-13T09:08:11.067Z
What is "all the $k'$-clauses" with respect to $k$ ?
Marzio De Biasi
CC BY-SA 4.0
2022-05-13T09:57:47.340Z
@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.
Xavier Labouze
CC BY-SA 4.0
2022-05-13T10:04:31.813Z
@MarzioDeBiasi Tks for your comment, I edit the post to clarify the point.
Xavier Labouze
CC BY-SA 4.0
2022-05-16T10:12:21.593Z
Ok, thanks for the clarification. Another question, before trying to find a reduction, what is the complexity of checking if a $k$-CNF formula is complete? (if you know it)
Marzio De Biasi
CC BY-SA 4.0
2022-05-16T10:20:56.137Z
@MarzioDeBiasi I would say it is NP-complete since a complete $k$-CNF is satisfiable as long as it doesn't contain the empty cause.
Xavier Labouze
<cc.complexity-theory><np-hardness><complexity-classes><sat>
Complexity of the Complete (3,2) SAT problem?
Xavier Labouze
# Complexity of the Complete (3,2) SAT problem?

(Asked by: username_0 on 2022-05-12)

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?](https://cstheory.stackexchange.com/questions/18379/complexity-of-the-3-2-s-sat-problem) where it concerned non complete formulas.)

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, sat

> **Comments:**
> **username_1**: It does not matter whether $F_2$ is complete or not, as you can compute the completion of a 2-CNF in polynomial time.  
> **username_0**: True, for $F_2$, it doesn't matter.  
> **username_2**: What is "all the $k'$-clauses" with respect to $k$ ?  
> **username_0**: @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.  
> **username_0**: @MarzioDeBiasi Tks for your comment, I edit the post to clarify the point.  
> **username_2**: Ok, thanks for the clarification. Another question, before trying to find a reduction, what is the complexity of checking if a $k$-CNF formula is complete? (if you know it)  
> **username_0**: @MarzioDeBiasi I would say it is NP-complete since a complete $k$-CNF is satisfiable as long as it doesn't contain the empty cause.  

---

## 1 answers

### Answer by username_3 on 2022-05-16. Score: 2 | Accepted answer

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:**
> **username_0**: Quite convincing, thank you !  

---

