TAOCP 7.2.2.2 Exercise 204

Section 7.2.2.2: Satisfiability

Exercise 204. ▶ [28] [28] Figure 46 might suggest that 3SAT problems on $n$ variables are always easy when there are fewer than $2n$ clauses. We shall prove, however, that any set of $m$ ternary clauses on $n$ variables can be transformed mechanically into another set of ternary clauses on $N = O(m)$ variables in which no variable occurs more than four times. The transformed problem is satisfiable if and only if the original problem was; thus it isn't any simpler, although (with at most $4N$ literals) it has at most $\frac{4}{3}N$ clauses.

a) First replace the original $m$ clauses by $m$ new clauses $(X_1 \vee X_2 \vee X_2), \ldots, (X_{3m-2} \vee X_{3m-1} \vee X_{3m})$, on $3m$ new variables, and show how to add $3m$ clauses of size 2 so that the resulting $4m$ clauses have exactly as many solutions as the original. b) Construct 16 unsatisfiable ternary clauses on 15 variables, where each variable occurs at most 4 times. Hint: If $F$ and $F'$ are two sets of clauses, let $F \sqcup F'$ stand for any other set obtained from $F \cup F'$ by replacing one or more clauses $C$ of $F$ by $x \cup C$ and one or more clauses $C'$ of $F'$ by $\bar{x} \cup C'$, where $x$ is a new variable; then $F \sqcup F'$ is unsatisfiable whenever $F$ and $F'$ are both unsatisfiable. For example, if $F = {c}$ and $F' = {1, 1}$, then $F \sqcup F'$ is either ${2, 12, 12}$ or ${1, 2, 12}$ or ${2, 12, 1}$. c) Remove one of the clauses from solution (b) and find all solutions of the 15 clauses that remain (exactly three of the variables will have two solutions). d) Use (a), (b), and (c) to prove the $N$-variable result claimed above.

Verified: no
Solve time: 6m35s

The previous text does not contain a proposed solution to Exercise 7.2.2.2.204. It contains a proposed solution and reviews for Exercise 7.2.2.2.203, which is a different problem about Model RB random satisfiability. A corrected solution to Exercise 7.2.2.2.204 requires the actual constructions for:

1. the 3SAT occurrence-splitting gadget in part (a),
2. the explicit 16-clause, 15-variable unsatisfiable gadget in part (b),
3. the exact satisfying assignments after deleting one clause in part (c),
4. the final bounded-occurrence reduction in part (d).

In particular, part (c) depends on the exact gadget chosen in part (b). Different valid 16-clause gadgets obtained from the $\sqcup$ construction can have different sets of remaining solutions after one clause is removed. Without the actual proposed gadget or the missing continuation of the previous solution, any explicit list of 15-clause solutions would be a guess rather than a rigorous derivation.

A correct solution must begin by specifying the exact clauses in part (b), verify that every variable occurs at most four times, then analyze the remaining formula in part (c). The reduction in part (d) depends on those exact clauses, because the gadget is used to replace high-occurrence variables while preserving satisfiability.

Please provide the proposed solution to Exercise 7.2.2.2.204 itself (especially the 16-clause construction and the claimed 15-clause solution set), and I can produce a fully corrected TAOCP-style solution.