TAOCP 7.2.2.2 Exercise 363

Section 7.2.2.2: Satisfiability

Exercise 363. ▶ [M30] (Lattices of partial assignments.) A partial assignment to the variables of a satisfiability problem is called stable (or "valid") if it is consistent and cannot be extended by unit propagation. In other words, it's stable if and only if no clause is entirely false, or entirely false except for at most one unassigned literal. Variable $x_k$ of a partial assignment is called constrained if it appears in a clause where $\bar{x}_k$ is true but all the other literals are false (thus its value has a "reason").

The $3^n$ partial assignments of an $n$-variable problem can be represented either as strings $x = x_1 \ldots x_n$ over the alphabet ${0, 1, }$ or as sets $L$ of pairwise distinct literals. For example, the string $x = 101$ corresponds to the set $L = {2, \bar{4}, 5}$. We write $x \prec x'$ if $x'$ is equal to $x$ except that $x_k = * $ and $x'_k \in {0, 1}$; equivalently $L \prec L'$ if $L' = L \cup k$ or $L' = L \cup \bar{k}$. Also $x \sqsubseteq x'$ if there are $t \ge 0$ stable partial assignments $x^{(j)}$ with

$$x = x^{(0)} \prec x^{(1)} \prec \cdots \prec x^{(t)} = x',$$

Let $p_1, \ldots, p_n, q_1, \ldots, q_n$ be probabilities, with $p_k + q_k = 1$ for $1 \le k \le n$. Define the weight $W(x)$ of a partial assignment to be 0 if $x$ is unstable, otherwise

$$W(x) = \prod{p_k \mid x_k = *} \cdot \prod{q_k \mid x_k \ne * \text{ and } x_k \text{ is unconstrained}}.$$

[E. Maneva, E. Mossel, and M. J. Wainwright, in JACM 54 (2007), 17:1–17:41, studied general message-passing algorithms on partial assignments that are distributed with probability proportional to their weights, in the case $p_1 = \cdots = p_n = p$, showing that survey propagation (Algorithm S) corresponds to the limit as $p \to 1$.]

a) True or false: The partial assignment specified by the literals currently on the trail in step C5 of Algorithm C is stable. b) What weights $W(x)$ correspond to the clauses $F$ in (1)? c) Let $x$ be a stable partial assignment with $x_k = 1$, and let $x'$ and $x''$ be obtained from $x$ by setting $x'_k \leftarrow 0$, $x''_k \leftarrow *$. True or false: $x'k$ is unconstrained in $x'$ if and only if (i) $x'$ is consistent; (ii) $x'$ is stable; (iii) $x''$ is stable. d) If the only clause is $123 = (x_1 \vee x_2 \vee x_3)$, find all sets $L$ such that $L \subseteq {1, 2, 3}$. e) What are the weights when there's only a single clause $123 = (x_1 \vee x_2 \vee x_3)$? f) Find clauses such that the sets $L$ with $L \subseteq {1, 2, 3}$ are $\emptyset$, ${4}$, ${5}$, ${1, 4}$, ${2, 5}$, ${4, 5}$, ${1, 4, 5}$, ${2, 4, 5}$, ${3, 4, 5}$, ${1, 3, 4, 5}$, ${2, 3, 4, 5}$, ${1, 2, 3, 4, 5}$. g) Let $\mathcal{L}$ be a family of sets $\subseteq {1, \ldots, n}$, closed under intersection, with the property that $L \in \mathcal{L}$ implies $L = L^{(0)} \prec L^{(1)} \prec \cdots \prec L^{(t)} = {1, \ldots, n}$ for some $L^{(j)} \in \mathcal{L}$. (The sets in (d) form one such family, with $n = 5$.) Construct strict Horn clauses with the property that $x$ is stable if and only if $L \subseteq {1, \ldots}$. h) True or false: If $L$, $L'$, $L''$ are stable and $L' \prec L$, $L'' \prec L$, then $L' \cap L''$ is stable. i) If $L' \subseteq L$ and $L' \subseteq L''$, prove that $L' \cap L''$ is stable. j) Prove that $\sum{x'} W(x') = \prod{p_k \mid x_k = *}$ whenever $x$ is stable.

Verified: no
Solve time: 3m48s

Solution

The information provided is not sufficient to derive the requested formulas.

Exercise 7.2.2.2.357 depends on equation (155) and on the definition of the quantities $\pi_0$, $\pi_s$, the “field” of a variable $v$, and the parameter $r$ in the surrounding text. The supplied section excerpt ends before the material containing equation (155), so the relationships needed to express

$$ x=\pi_0,\qquad y=\pi_s $$

in terms of $p$, $q$, and $r$ are not available.

A complete solution requires the definitions preceding equation (155), specifically:

the meaning of the field $(p,q)$ of the variable $v$,
the recurrence or relation involving $\pi_i$,
the role of the parameter $r$ in that recurrence.

Without those definitions, there is no justified derivation of $x$ and $y$, and any proposed formulas would be unsupported.

Please provide the text surrounding equation (155), including the definition of $\pi_0$ and $\pi_s$, and the complete solution can then be derived.