TAOCP 7.2.2.2 Exercise 324

Section 7.2.2.2: Satisfiability

Exercise 324. ▶ [22] [22] Given a trace $\alpha = x_1 x_2 \ldots x_n$ for a graph $G$, explain how to find all strings $\beta$ that are equivalent to $\alpha$, using Algorithm 7.2.1.2V. How many strings yield (136)?

Verified: no
Solve time: 3m47s

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. ∎