TAOCP 7.2.2.2 Exercise 145

Section 7.2.2.2: Satisfiability

Exercise 145. [23] [23] Starting with $h(l) = 1$ for each of the 18 literals $l$ in $\mathit{waerden}(3,3;9)$, find successively refined estimates $h'(l)$, $h''(l)$, $\ldots$, using (65) with respect to the 32 ternary clauses (9). Then, assuming that $x_3$ has been set false as in exercise 136, and that the resulting binary clauses 13, 19, 28, 34, 37, 46, 67, 79 have been included in the BIMP tables, do the same for the 16 literals that remain at depth $d = 1$.

Verified: no
Solve time: 3m05s

---

The exercise, as stated in the prompt, cannot be solved because it omits the data that determine the requested numerical values.

The requested computation is not symbolic. It requires repeated numerical evaluation of the heuristic update defined by equation (65) on a specific SAT instance. In particular, the following information is indispensable:

1. The exact definition of the refinement rule (65), which specifies how to compute

$$ h'(l) $$

from the current values $h(\cdot)$. 2. The complete list of the $32$ ternary clauses comprising

$$ \mathit{waerden}(3,3;9), $$

referenced as display (9). 3. For the second part, the precise reduced formula obtained after assigning

$$ x_3=\mathrm{false}, $$

together with the resulting BIMP tables containing the binary clauses numbered

$$ 13,\ 19,\ 28,\ 34,\ 37,\ 46,\ 67,\ 79, $$

exactly as described in Exercise 136.

Once these data are available, the computation proceeds as follows.

For the original instance:

1. Initialize

$$ h(l)=1 $$

for each of the $18$ literals. 2. Apply equation (65) simultaneously to every literal using all $32$ ternary clauses to obtain the first refinement

$$ h'(l). $$ 3. Use $h'(l)$ as the new input and apply (65) again to obtain

$$ h''(l). $$ 4. Continue in the same manner to obtain

$$ h'''(l),\ h^{(4)}(l),\ \ldots $$

until the requested successive refinements have been produced.

For the reduced instance:

1. Assign

$$ x_3=\mathrm{false}. $$ 2. Remove the satisfied and falsified literals as prescribed in Exercise 136. 3. Insert the eight resulting binary clauses into the BIMP tables. 4. Initialize the remaining $16$ literals with

$$ h(l)=1. $$ 5. Apply equation (65) repeatedly on this reduced formula to obtain

$$ h'(l),\ h''(l),\ \ldots $$

for the remaining literals.

No numerical table can be derived from the information contained in the prompt alone. The values depend explicitly on the omitted equation (65) and the omitted clause lists. Any explicit numbers would therefore be unsupported.

Hence the correct resolution is that the exercise cannot be completed from the material provided. To produce the requested tables of $h'(l), h''(l), \ldots$, one must first supply the text of equation (65), the $32$ clauses of display (9), and the reduced instance described in Exercise 136.