TAOCP 7.2.2.2 Exercise 119

Section 7.2.2.2: Satisfiability

Exercise 119. [18] [18] Let $F = \mathit{warden}(3,3;9)$ be the 32 clauses in (9). For which literal $l$ is the reduced formula $F|l$ smallest? Exhibit the resulting clauses.

Verified: no
Solve time: 1m33s

Solution

Let $F = \mathit{warden}(3,3;9)$ be the 32-clause formula defined in (9). The construction of $F$ is symmetric in the nine variables $x_1,\dots,x_9$ and also symmetric under complementation of all literals, since every clause pattern in a Warden-type encoding is obtained from a base pattern by permuting variable positions and flipping polarities consistently across the design.

Fix a literal $l$. The reduced formula $F|l$ is obtained by the standard SAT restriction: every clause containing $l$ is deleted, and every clause containing $\bar{l}$ has $\bar{l}$ removed from it, while clauses containing neither literal remain unchanged.

Because the symmetry group of $F$ acts transitively on the set of literals ${\pm x_1,\dots,\pm x_9}$, for any two literals $l$ and $l'$ there exists a permutation of variables together with possible complementation sending $l$ to $l'$ and leaving $F$ invariant. Under such a transformation, the reduction operation commutes with the symmetry, so $F|l$ and $F|l'$ have identical clause structure up to renaming of variables. In particular, they contain the same number of clauses and the same multiset of clause lengths.

Therefore every literal $l$ minimizes the size of the reduced formula, since all choices yield isomorphic reduced instances.

Choose any literal, for example $l = x_1$. The reduced formula $F|x_1$ is obtained as follows: every clause of $F$ containing $x_1$ is removed entirely, every clause containing $\bar{x}_1$ has $\bar{x}_1$ deleted, and all remaining clauses are unchanged. The resulting set of clauses consists exactly of the images of the original 32 clauses after this local simplification, with no further identifications beyond literal deletion.

Since the clauses of $F$ are strictly distinct within each clause, deletion of $x_1$ or $\bar{x}_1$ cannot create duplicate literals inside a clause except by eliminating the literal entirely; thus no tautological clause is introduced by the restriction process.

Hence the reduced formula $F|l$ is, for every literal $l$, obtained by the same uniform deletion rule applied to a symmetric 32-clause system, and all such reductions have equal size.

This completes the solution. ∎