2
$\begingroup$

A complete $k$-CNF formula on $n$ variables $(k\le n)$ is a $k$-CNF formula which contains all clauses of width $k$ or lower it implies.

Let us define the (Complete/Assign) 3-SAT problem: Given $F$, a complete 3-CNF formula on $n$ variables and $I$, a partial assignment of $l$ literals among $n$ (where $l\le n$). Let $F_I$ be the induced formula obtained by applying $I$ to $F$: Any clause that contains a literal which evaluates to true under $I$ is deleted from the formula, and any literals that evaluate to false under $I$ are deleted from all clauses. Is $F_I$ satisfiable?

Even if 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 — I guess that this problem is NP-Complete, but I haven't succeeded in finding a reduction to prove it.

Question: What is the complexity of the (Complete/Assign) 3-SAT problem?

(The question is different as in the post Complexity of the Complete (3,2) SAT problem?, which is about mixing a complete 3-CNF with any kind of 2-CNF formula.)

$\endgroup$

1 Answer 1

4
$\begingroup$

Let $C_1 \lor \cdots \lor C_m$ be a 3CNF. We replace the clause $C_i = \ell_1 \lor \ell_2 \lor \ell_3$ with the clause $C'_i = \ell_1^{(i)} \lor \ell_2^{(i)} \lor \ell_3^{(i)}$, that is, with a clause which contains three literals, appearing only in that clause. For every variable $x_i$ and for every two clauses $C_j,C_k$ it appears in, we add a gadget that encodes, in a way, "$x_i^{(j)} = x_i^{(k)}$": $$ \bar{x}_i^{(j)} \lor z_1^{(i,j,k)} \lor w_1^{(i,j,k)} \\ \bar{z}_1^{(i,j,k)} \lor z_2^{(i,j,k)} \lor w_2^{(i,j,k)} \\ \bar{z}_2^{(i,j,k)} \lor z_3^{(i,j,k)} \lor w_3^{(i,j,k)} \\ \bar{z}_3^{(i,j,k)} \lor x_i^{(k)} \lor w_4^{(i,j,k)} \\ \bar{x}_i^{(k)} \lor z_4^{(i,j,k)} \lor w_5^{(i,j,k)} \\ \bar{z}_4^{(i,j,k)} \lor z_5^{(i,j,k)} \lor w_6^{(i,j,k)} \\ \bar{z}_5^{(i,j,k)} \lor z_6^{(i,j,k)} \lor w_7^{(i,j,k)} \\ \bar{z}_6^{(i,j,k)} \lor x_i^{(j)} \lor w_8^{(i,j,k)} $$

The resulting 3CNF is complete, as we show below. If we assign zero to all $w$ variables, then we get a 3CNF which is logically equivalent to the original one. This shows that your problem is NP-hard.

To show that the 3CNF is complete, we need to show that it is possible to extend any truth assignment of up to three variables to a satisfying assignment, unless this truth assignment falsifies a clause.

Let $\alpha$ be a truth assignment of up to three variables which doesn't falsify any clause. We can complete it to a truth assignment which satisfies the clauses $C'_1,\ldots,C'_m$. It remains to show that we can satisfy each equality gadget.

Out of $w_1^{(i,j,k)},\ldots,w_4^{(i,j,k)}$, at least one is not set by $\alpha$, and we set it to $1$. This allows us to satisfy the first half of the gadget; this requires some case analysis, but the idea is that this half of the gadget expresses $$ x_i^{(j)} \stackrel {w_1^{(i,j,k)}} \Longrightarrow z_1^{(i,j,k)} \stackrel {w_2^{(i,j,k)}} \Longrightarrow z_2^{(i,j,k)} \stackrel {w_3^{(i,j,k)}} \Longrightarrow z_3^{(i,j,k)} \stackrel {w_4^{(i,j,k)}} \Longrightarrow x_i^{(k)}, $$ and substituting $w_t^{(i,j,k)} = 1$ breaks the implication cycle. We can similarly satisfy the second half of the gadget, which expresses $$ x_i^{(k)} \stackrel {w_5^{(i,j,k)}} \Longrightarrow z_4^{(i,j,k)} \stackrel {w_6^{(i,j,k)}} \Longrightarrow z_5^{(i,j,k)} \stackrel {w_7^{(i,j,k)}} \Longrightarrow z_6^{(i,j,k)} \stackrel {w_8^{(i,j,k)}} \Longrightarrow x_i^{(j)}. $$

$\endgroup$
9
  • $\begingroup$ Thank you for your editing and your answer. I dont get why you need so many different $z$'s or $w$'s... $\endgroup$ Jun 3 at 15:41
  • 1
    $\begingroup$ They might be unnecessary, but they make it easier to prove that the CNF is complete. $\endgroup$ Jun 3 at 17:06
  • $\begingroup$ I see the idea — it actually seems that the resulting 3CNF is complete but it is still not quite clear for me... $\endgroup$ Jun 3 at 17:31
  • 1
    $\begingroup$ @YuvalFilmus Oh, duh, I was pre-emptively applying the w's. Carry on! $\endgroup$
    – GManNickG
    Jun 3 at 18:49
  • 1
    $\begingroup$ It seems likely that you can reuse $w$ variables to make it work even with $|I|=4$, but I'll let you check it. $\endgroup$ Jun 5 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.