TAOCP 7.2.2.2 Exercise 144

Exercise 144. [15] [15] True or false: If $l$ doesn't appear in any clause, $h'(l) = 0.1$ in (65).

Verified: no
Solve time: 3m05s

The previous solution fails because it assumes an additive constant survives normalization unchanged. In (65), $h'(l)$ is defined as a normalized quantity derived from weights assigned to literals, so every value depends on the global normalization over all literals. There is no independent “baseline term” that persists after normalization.

Let $h(l)$ denote the unnormalized contribution defined earlier in (65). In this scheme, $h'(l)$ is obtained by normalizing all $h(l)$ values over the set of literals, i.e. of the form

$$ h'(l) = \frac{h(l)}{\sum_{l'} h(l')}, $$

or an equivalent normalization in which all $h'(l)$ depend on the full vector $(h(l'))_{l'}$.

Now assume $l$ does not appear in any clause. Then, by the definition of the unnormalized weights in (65), it receives no contribution from any clause, so

$$ h(l) = 0. $$

However, normalization does not assign a fixed default value to such an element. Instead, it rescales all $h(l')$ simultaneously so that the total sum (or another global constraint specified in (65)) is satisfied. As a result, a zero entry remains zero after normalization:

$$ h'(l) = \frac{0}{\sum_{l'} h(l')} = 0, $$

provided the denominator is positive (as it must be for a well-defined normalization in the construction).

Therefore $h'(l)$ cannot equal $0.1$. Its value is determined entirely by the normalization of the entire system and, under the standard interpretation of (65), a literal with no occurrences contributes nothing both before and after normalization.

Hence the statement is false.