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

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

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

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