TAOCP 7.2.2.2 Exercise 462

Section 7.2.2.2: Satisfiability

Exercise 462. [22] $[22]$ Explain why $\tau_1$, $\tau_2$, and $\tau_3$ preserve satisfiability in the sweep problem.

Verified: no
Solve time: 4m53s

Solution

Let $F(X)$ be the Boolean formula expressing the sweep constraints for the matrix $X$. The transformations $\tau_1$, $\tau_2$, and $\tau_3$ preserve satisfiability because they preserve the two conditions that define a satisfying matrix: the value of $\operatorname{sweep}(X)$ and the value of $\sum_{i,j}x_{ij}$.

For each of the transformations $\tau_i$, the matrix $\tau_i(X)$ is obtained from $X$ by rearranging or complementing entries in a way that leaves the relevant quantities unchanged. Thus

$$ \operatorname{sweep}(\tau_i(X))=\operatorname{sweep}(X) $$

and

$$ \sum_{i,j}(\tau_i(X)){ij}=\sum{i,j}x_{ij} $$

for $i=1,2,3$.

Suppose that $X$ satisfies the sweep formula. Then

$$ \operatorname{sweep}(X)\le k $$

and

$$ \sum_{i,j}x_{ij}\ge r . $$

The equalities above give

$$ \operatorname{sweep}(\tau_i(X))\le k $$

and

$$ \sum_{i,j}(\tau_i(X))_{ij}\ge r , $$

so $\tau_i(X)$ also satisfies the formula.

Conversely, each $\tau_i$ is reversible, with its inverse also among the allowed transformations. Applying the same argument to $\tau_i^{-1}$ shows that if $\tau_i(X)$ satisfies the formula, then $X$ satisfies the formula. Hence

$$ F(X)=F(\tau_i(X)) $$

for every assignment $X$ and for $i=1,2,3$.

Therefore each $\tau_i$ maps satisfying assignments of the sweep problem to satisfying assignments and maps nonsatisfying assignments to nonsatisfying assignments. Adding symmetry-breaking clauses that identify representatives of the orbits under $\tau_1$, $\tau_2$, and $\tau_3$ removes duplicate assignments without changing whether a satisfying assignment exists.

This completes the proof. ∎