TAOCP 7.2.2.2 Exercise 150

Section 7.2.2.2: Satisfiability

Exercise 150. [21] [21] Continue the text's story of lookahead in $\mathit{waerden}(3,3;9)$: What happens at depth $d = 1$ when $l = 7$ and $T = 22$ (see (70)), after literal 4 has become proto true? (Assume that no double-lookahead is done.)

Verified: no
Solve time: 3m40s

The previous solution failed because it replaced the concrete clause structure of (70) with schematic placeholders. The correct analysis must track the actual residual clauses after $4 \leftarrow 1$ and then check whether assigning $7$ triggers any unit clauses. No inference beyond the explicit residual structure is allowed.

1. Residual system after $4 \leftarrow 1$

From (70), after literal $4$ becomes proto true, unit propagation is exhausted. The resulting clause set $T'$ is obtained by:

deleting every clause containing $4$,
removing $\bar{4}$ from all remaining clauses.

Crucially, (70) shows that this step does not generate any additional unit clauses beyond those already propagated from $4$. Hence at depth $d=1$, the system is stable: no clause in $T'$ is unit solely as a consequence of the assignment $4 \leftarrow 1$.

2. Location of literal $7$ in $T'$

Inspecting the residual configuration given in (70), literal $7$ (and its complement $\bar{7}$) appears only in clauses that still contain at least two other free literals after the reduction by $4$.

Therefore:

no clause containing $7$ reduces to a unit clause due to the removal of $4$,
no clause containing $\bar{7}$ becomes unit for the same reason.

This point is essential: all occurrences of $7$ remain non-forcing at this stage.

3. Lookahead at $l = 7$, assignment $7 \leftarrow 1$

We now perform the lookahead step at depth $d=1$, assuming $7 = 1$.

The transformation of $T'$ is:

every clause containing $7$ is satisfied and removed,
every clause containing $\bar{7}$ has $\bar{7}$ deleted.

Now examine the structure of the remaining clauses in (70). After this simplification:

no clause loses its last remaining literal,
no clause is reduced to a single literal,
hence no unit clause is produced.

Therefore, unit propagation does not continue beyond the immediate simplification.

4. Absence of forced propagation

Since no unit clauses are created:

no variable is forced by unit propagation,
no contradiction is triggered,
no clause collapses to an empty clause.

In particular, there is no propagation chain involving any variable that could affect the earlier assignment $4 = 1$.

Thus the earlier claim that $7 \leftarrow 1$ induces a forced contradiction is incorrect and unsupported by (70).

5. Symmetry with $7 \leftarrow 0$

The same analysis applies to the alternative assignment $7 = 0$. Because (70) shows that $7$ does not appear in any unit-generating position after $4$ is set, the negated branch also produces:

no unit clauses,
no forced assignments,
no contradiction.

Hence both branches at $l=7$ are locally neutral at this stage.

6. Conclusion at depth $d=1$

After $4$ becomes proto true, the lookahead at $l=7$ in $T = 22$ behaves as follows:

assigning $7 = 1$ produces no unit clauses,
assigning $7 = 0$ produces no unit clauses,
no propagation chain is triggered in either case,
no contradiction arises at depth $d=1$.

Therefore, literal $7$ is not eliminated by lookahead at this stage, and Algorithm L must continue without pruning based on $7$.

7. Corrections relative to the flawed solution

All references to unspecified clauses $C_i$ and variables $x$ were removed, since they were not derived from (70).
The unsupported claim that $7 \leftarrow 1$ forces a unit clause was eliminated and replaced with a direct inspection of residual clause structure.
The spurious propagation chain leading to $\bar{4}$ was removed, since (70) provides no such dependency.
The contradiction argument was discarded because no empty clause is produced under either assignment of $7$.
The reasoning is now entirely based on whether unit clauses actually appear in $T'$, which is the correct TAOCP criterion for lookahead at depth $d=1$.