TAOCP 7.2.2.2 Exercise 138

Step L9 of Algorithm L operates purely as a local propagation step over the binary implication lists.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.2: Satisfiability

Exercise 138. [20] Discuss what happens in step L9 of Algorithm L if we happen to have both $\bar{v} \in \text{BIMP}(\bar{u})$ and $\bar{u} \in \text{BIMP}(\bar{v})$.

Verified: no
Solve time: 2m01s

Step L9 of Algorithm L operates purely as a local propagation step over the binary implication lists. For each processed literal $l$, it scans $\mathrm{BIMP}(l)$ and activates or enqueues each $l' \in \mathrm{BIMP}(l)$ as a consequence of the implication $l \rightarrow l'$. No structural identification of variables is performed, and no global equivalence reasoning is carried out in this step.

Assume now that

$$ \bar{v} \in \mathrm{BIMP}(\bar{u}) \quad \text{and} \quad \bar{u} \in \mathrm{BIMP}(\bar{v}). $$

This means that during execution:

  • when $\bar{u}$ is processed in step L9, the algorithm encounters $\bar{v} \in \mathrm{BIMP}(\bar{u})$ and therefore generates or schedules $\bar{v}$;
  • when $\bar{v}$ is processed in step L9, the algorithm encounters $\bar{u} \in \mathrm{BIMP}(\bar{v})$ and therefore generates or schedules $\bar{u}$.

Thus step L9 produces a 2-cycle of propagated activations:

$$ \bar{u} \leadsto \bar{v} \leadsto \bar{u}. $$

The mechanical effect depends on the bookkeeping convention used for the propagation list in Algorithm L. In all cases, the key point is that L9 performs only local insertions into the work structure:

  • If the algorithm allows duplicates in the pending list, then $\bar{u}$ and $\bar{v}$ may each be inserted multiple times.
  • If the algorithm marks literals as already scheduled or already active, then the second insertion of an already scheduled literal has no effect.

In either case, the mutual membership produces no new structural change beyond this repetition. The propagation stabilizes because both implications are already accounted for once each direction has been processed.

Crucially, step L9 does not perform any higher-level operation such as merging variables, computing strongly connected components, or identifying equivalence classes. It only executes the immediate consequence of each binary implication by placing implied literals into the active or pending set.

Therefore, when both $\bar{v} \in \mathrm{BIMP}(\bar{u})$ and $\bar{u} \in \mathrm{BIMP}(\bar{v})$ hold, step L9 simply causes each of $\bar{u}$ and $\bar{v}$ to trigger the other’s insertion into the propagation structure, resulting in a benign two-element cycle of scheduled implications with no additional algorithmic effect beyond possible redundant enqueuing.