Complexity of the (Complete/Assign) 3-SAT problem?

Question

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

Answer 1

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