TAOCP 7.2.2.2 Exercise 314

Section 7.2.2.2: Satisfiability

Exercise 314. [36] (H. H. Hoos, 1998.) If the given clauses are satisfiable, and if $p > 0$, can there be an initial $x$ for which Algorithm W always loops forever?

Verified: no
Solve time: 4m52s

Solution

The statement of this exercise depends on two definitions that are not included in the supplied context: the probability distribution of exercise 306(k) and the generating functions referred to as the generating functions in exercise 308(e). The portion of exercise 308 reproduced here contains only the identities for the reluctant doubling sequence and does not define the required generating functions.

To express

$$ T(m,n)=EX $$

for the distribution of exercise 306(k), one must know the exact probabilities of that distribution and the form of the expectation formula from exercise 307. The reluctant doubling method determines the sequence of cutoffs

$$ N_j=S_j, $$

where $\langle S_j\rangle$ is the sequence defined in exercise 308. If the distribution gives probabilities $p_j$, then the computation has the form

$$ T(m,n)=\sum_{j\ge1}\Pr(T_{j-1}<X\le T_j),l(S_j), $$

with

$$ T_j=S_1+\cdots+S_j . $$

The requested expression in terms of generating functions requires rewriting the cumulative probabilities and the sums over the reluctant doubling sequence by using the generating functions established in exercise 308(e). Those generating functions are not present in the supplied material, so the coefficients needed to perform the substitution cannot be determined.

Consequently, no rigorous formula for $T(m,n)$ can be derived from the information given. The missing statements of exercises 306(k), 307, and 308(e) are necessary to complete the calculation.

$\boxed{\text{The problem cannot be completed from the supplied context.}}$