TAOCP 7.2.2.2 Exercise 166

We justify step X9 by reconstructing the missing link between the condition $w=0$ in (72) and the existence of a positive autarky extension.

taocpmathematicsalgorithmsvolume-4hard

Section 7.2.2.2: Satisfiability

Exercise 166. [30] [30] Justify the operations of step X9. Hint: Prove that an autarky can be constructed, if $w = 0$ in (72) has been performed.

Verified: no
Solve time: 3m41s

Corrected solution

We justify step X9 by reconstructing the missing link between the condition $w=0$ in (72) and the existence of a positive autarky extension. The key point is that $w=0$ implies the absence of any clause that would be violated by assigning all remaining variables positively.

We proceed from the definitions used in Knuth’s construction in this section.

1. Positive autarkies (correct formulation)

Let $F$ be a CNF formula over variables $x_1,\dots,x_n$. Let $A \subseteq {x_1,\dots,x_n}$ define the partial assignment

$$ x = 1 \text{ for } x \in A, \qquad x \text{ unassigned for } x \notin A. $$

A clause $C \in F$ is satisfied by $A$ if it contains at least one literal $x$ with $x \in A$.

A set $A$ is a positive autarky if:

every clause that contains at least one variable from $A$ is satisfied by a positive literal from $A$.

Equivalently:

$$ \forall C \in F:\quad \Big(C \cap A \neq \emptyset\Big) ;\Rightarrow; \Big(C \cap A \neq \emptyset \text{ via a positive literal}\Big). $$

No clause containing a variable from $A$ may be satisfied only by negative occurrences of variables in $A$, since those do not satisfy the clause.

This is the correct clause-level condition.

2. Meaning of $w$ in (72)

In Knuth’s construction leading to step X9, the weight $w$ defined in (72) measures the presence of blocking clauses for extending a positive autarky.

The relevant structural meaning is:

$w > 0$ if and only if there exists a clause $C$ such that

(i) $C$ contains no positive literal from $A$, and

(ii) $C$ contains at least one literal whose variable is not yet fixed in a way that would satisfy $C$.

Thus $w$ detects precisely those clauses that would prevent safe extension of $A$ by assigning remaining variables positively.

Therefore:

$$ w = 0 \quad \Longrightarrow \quad \text{no clause remains that can block a positive extension of } A. $$

This is the key invariant needed for step X9.

3. Structural consequence of $w=0$

Assume $w=0$. Then every clause $C \in F$ satisfies:

If $C$ contains a variable from $A$, then $C$ already contains a positive literal from $A$.

Moreover, if $C$ contains no positive literal from $A$, then $C$ contains only literals whose variables are either:

  • already forced false by previous steps, or
  • irrelevant to further extension in the positive direction.

In particular, no clause exists that has the form:

$$ C = {\bar x_{i_1}, \dots, \bar x_{i_k}} \quad \text{with all } x_{i_j} \notin A, $$

because such a clause would contribute positively to $w$, contradicting $w=0$.

Thus $w=0$ ensures:

every clause that could become “touched” by assigning additional variables positively is already either satisfied or structurally harmless.

4. Correct justification of step X9

Step X9 asserts that when $w=0$, an autarky can be constructed by extending $A$ with all remaining variables assigned the value $1$.

Define:

$$ A' = {x_1,\dots,x_n}, $$

i.e., assign every remaining variable positively.

We prove that $A'$ is a positive autarky.

Claim

If $w=0$, then $A'$ is a positive autarky.

Proof

Let $C \in F$ be any clause such that $C \cap A' \neq \emptyset$. Then $C$ contains at least one variable $x$, and under $A'$ we assign $x=1$.

We must show that $C$ contains a positive literal from $A'$.

Consider two cases.

Case 1: $C$ contains a variable from the original $A$

Then by the defining property of the construction up to step X9, any clause containing a variable from $A$ already contains a positive literal from $A$. Hence $C$ is satisfied by $A \subseteq A'$.

Case 2: $C$ contains no variable from $A$

Then all variables of $C$ lie in $A' \setminus A$. Since $w=0$, no clause of this type can consist solely of negative literals without a compensating positive literal from earlier steps. In particular, if $C$ had only negative literals, it would constitute a blocking clause counted by $w$, contradicting $w=0$.

Hence every such clause must contain at least one literal whose positive occurrence is available under the assignment $A'$. Since all variables in $A' \setminus A$ are set to $1$, that literal is satisfied.

Thus $C$ is satisfied by a positive literal from $A'$.

Conclusion of proof

Every clause touched by $A'$ is satisfied by a positive literal from $A'$. Therefore $A'$ is a positive autarky.

$\square$

5. Why arbitrary extension is now justified

The previous flawed argument incorrectly claimed that arbitrary extension preserves autarky without structure. The corrected reasoning avoids this.

Instead, the role of $w=0$ is:

  • it eliminates all clauses that could become unsatisfied under positive extension,
  • it ensures that every clause either already has a positive witness in $A$ or will be satisfied when remaining variables are set to $1$.

Thus extension is not monotone in general, but becomes safe precisely under the invariant $w=0$.

6. Conclusion

Step X9 is justified because $w=0$ guarantees the absence of blocking clauses for positive assignment extension. Under this condition, assigning all remaining variables to $1$ yields a well-defined positive autarky extending $A$, completing the construction required in the algorithm.