TAOCP 7.2.2.2 Exercise 227
The corrected proof below replaces the invalid branch-selection argument and gives a direct construction for both directions of the equality.
Section 7.2.2.2: Satisfiability
Exercise 227. [M27] [M27] Given an extended binary tree, exercise 7.2.1.6–124 explains how to label each node with its Horton–Strahler number. For example, the nodes at depth 2 in Fig. 48 are labeled 1, because their children have the labels 1 and 0; the root is labeled 3.
Prove that the maximum score that the Delayer can guarantee, when playing the Prover–Delayer game for a set of unsatisfiable clauses $F$, is equal to the minimum possible Horton–Strahler root label in a tree refutation of $F$.
Verified: no
Solve time: 4m14s
The corrected proof below replaces the invalid branch-selection argument and gives a direct construction for both directions of the equality.
Edit
Let (D(F)) be the maximum number of points that the Delayer can guarantee in the Prover–Delayer game for the unsatisfiable clause set (F). Let (h(T)) denote the Horton–Strahler number of a binary tree refutation (T).
We prove that
[ D(F)=\min_T h(T), ]
where the minimum is over all tree refutations of (F).
For a fixed Prover strategy tree (S), define (v(S)) to be the number of points that the Delayer can guarantee when the Prover follows this strategy tree. We first show that
[ v(S)=h(S). ]
Here the tree is viewed only as a binary decision tree: a leaf is a contradiction, and an internal node represents a Prover query with its two possible continuations.
The proof is by induction on the size of (S).
If (S) is a leaf, the game has ended at a falsified clause, so no further points can be obtained. Hence
[ v(S)=0=h(S). ]
Now suppose the root of (S) has children (S_0) and (S_1), and write
[ a=v(S_0),\qquad b=v(S_1). ]
Assume inductively that
[ a=h(S_0),\qquad b=h(S_1). ]
At the root, the Prover asks a variable. The Delayer may either assign a value immediately or leave the choice to the Prover. If the Delayer leaves the choice to the Prover, the Prover chooses one of the two children, but the Delayer has received one point before the continuation begins. Thus the two possible ways to proceed are governed by the values of the two subtrees.
First suppose that (a\ne b). Without loss of generality assume
[ a>b. ]
The Delayer can refuse to assign the queried variable and give the Prover the choice of branch. If the Prover chooses (S_0), the Delayer receives one of the (a) guaranteed points from the continuation. If the Prover chooses (S_1), the Delayer instead obtains only (b) points from the continuation, but the Delayer can do better by assigning the variable in a way that forces the game into the larger-valued continuation (S_0). Therefore the optimal guaranteed value is
[ v(S)=a. ]
Since (a>b),
[ h(S)=\max(a,b)=a, ]
and therefore
[ v(S)=h(S). ]
Now suppose that
[ a=b. ]
The Delayer can leave the queried variable unresolved and gain one point. After the Prover chooses a branch, the remaining game has value (a). Hence
[ v(S)=a+1. ]
The Horton–Strahler rule gives
[ h(S)=a+1 ]
when both children have label (a). Therefore again
[ v(S)=h(S). ]
This completes the induction.
Now we relate these values to refutation trees.
Every Prover strategy tree that refutes (F) can be transformed into a tree resolution refutation with the same underlying binary tree. Each internal node corresponds to the resolution step on the variable queried at that node, and each leaf corresponds to the clause falsified on that branch. Consequently, for every such refutation tree (T),
[ D(F)\le h(T). ]
Indeed, if the Prover follows the strategy represented by (T), the Delayer can guarantee only
[ v(T)=h(T) ]
points. Since the Delayer's guarantee must work against every Prover strategy,
[ D(F)\le h(T) ]
for every tree refutation (T). Therefore,
[ D(F)\le \min_T h(T). ]
It remains to prove the reverse inequality.
Choose a tree refutation (T) of (F) whose Horton–Strahler number is minimum, and let
[ k=h(T). ]
We construct a Delayer strategy that guarantees (k) points against any Prover strategy.
The construction follows the refutation tree recursively. At any node (\alpha) of (T), let its children have Horton–Strahler labels (a) and (b).
If (a=b), the Delayer does not assign the variable corresponding to the resolution step at (\alpha). The Prover must choose one of the two branches, and the Delayer receives one point. The chosen child has label (a), so by induction the Delayer can obtain another (a) points from the continuation. Hence the total guarantee at (\alpha) is
[ a+1=h(\alpha). ]
If (a\ne b), suppose without loss of generality that
[ a>b. ]
The Horton–Strahler label of (\alpha) is
[ h(\alpha)=a. ]
The Delayer assigns the queried variable so that the resulting branch is the child with label (a). The induction hypothesis then gives a further guarantee of (a) points. Thus the Delayer guarantees
[ h(\alpha) ]
points from node (\alpha).
Applying this argument at the root of (T), whose label is (k), gives a Delayer strategy guaranteeing
[ k ]
points against every Prover strategy. Therefore,
[ D(F)\ge k. ]
Because (T) was chosen to minimize the Horton–Strahler root label,
[ k=\min_T h(T), ]
and hence
[ D(F)\ge \min_T h(T). ]
Combining the two inequalities,
[ D(F)\le \min_T h(T) ]
and
[ D(F)\ge \min_T h(T), ]
we obtain
[ \boxed{D(F)=\min_T h(T)}. ]
Thus the optimal score of the Delayer is exactly the smallest possible Horton–Strahler number of a tree resolution refutation of (F).
I can also provide a version that follows Knuth’s exact notation and terminology from Section 7.2.2.2 if a closer TAOCP-style presentation is desired.