TAOCP 7.2.2.2 Exercise 364

Section 7.2.2.2: Satisfiability

Exercise 364. ▶ [M21] A covering assignment is a stable partial assignment in which every assigned variable is constrained. A core assignment is a covering assignment $L$ that satisfies $L \subseteq L'$ for some covering assignment $L'$.

a) True or false: The empty partial assignment $L = \emptyset$ is always covering. b) Find all the covering and core assignments of the clauses $F$ in (1). c) Find all the covering and core assignments of the clauses $R'$ in (7). d) Show that every satisfying assignment $L'$ has a unique core. e) The satisfying assignments form a graph, if two of them are adjacent when they differ by exactly one literal. The connected components of this graph are called clusters. Prove that the elements of each cluster have the same core. f) If $L'$ and $L''$ have the same core, do they belong to the same cluster?

Verified: no
Solve time: 3m44s

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:

1. the meaning of the field $(p,q)$ of the variable $v$,
2. the recurrence or relation involving $\pi_i$,
3. 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.