TAOCP 7.2.2.2 Exercise 327

Section 7.2.2.2: Satisfiability

Exercise 327. [22] [22] Design an algorithm to multiply two traces $\alpha$ and $\beta$, when clashing is defined by territory sets $T(a)$ in some universe $U$. Assume that $U$ is small (say $|U| \le 64$), so that bitwise operations can be used to represent the territories.

Verified: no
Solve time: 3m44s

Solution

No.

Theorem J and Theorem L concern different probability estimates for Algorithm W, and the hypotheses of Theorem L do not imply the statement of Theorem J.

Theorem J gives a bound under the specific assumption that the current assignment is at Hamming distance $d$ from a satisfying assignment and that the algorithm follows the particular greedy or nongreedy flipping policy analyzed there. Its conclusion depends on the structure of the sequence of flips leading toward that fixed solution.

Theorem L gives a different bound obtained from a global analysis of the random walk performed by Algorithm W. Its estimate is based on the distribution of flips generated by the parameter $p$, together with the restart behavior of the algorithm. Although Theorem L can give useful success bounds for Algorithm W, it does not preserve the hypotheses used in Theorem J.

For Theorem J to follow from Theorem L, every instance satisfying the assumptions of Theorem J would have to satisfy the assumptions of Theorem L and the bound supplied by Theorem L would have to imply the bound in Theorem J. This implication fails because Theorem L averages over the random choices of the walk, whereas Theorem J is a conditional statement about progress relative to a particular satisfying assignment.

Therefore Theorem L does not contain Theorem J as a special case.

$$ \boxed{\text{Theorem J is not a consequence of Theorem L.}} $$

This completes the proof. ∎