TAOCP 7.2.2.2 Exercise 259

Section 7.2.2.2: Satisfiability

Exercise 259. [M20] Can $\text{ACT}(j)$ exceed $\text{ACT}(k)$ for values of $p$ near 0 or 1, but not for all $p$?

Verified: no
Solve time: 3m39s

Solution

No.

The parameter $p$ is the probability used in Algorithm C when choosing a decision literal. The activity scores $\operatorname{ACT}(j)$ and $\operatorname{ACT}(k)$ are not functions of $p$ alone. They are determined by the sequence of conflicts and learned clauses, because the activity of a variable is changed only when the algorithm updates activities after conflicts.

Changing $p$ changes the probability distribution of the search path, but it does not change the activity-update rule. For any fixed execution history, the values of

$$ \operatorname{ACT}(j) $$

and

$$ \operatorname{ACT}(k) $$

are fixed numbers, independent of the value of $p$ used to choose decisions during that execution.

Suppose that for some value of $p$ we obtain an execution in which

$$ \operatorname{ACT}(j)>\operatorname{ACT}(k). $$

The inequality is then a consequence of the particular conflicts and learned clauses that occurred in that execution. If another value of $p$ leads to the same sequence of decisions and propagations, the same inequality holds. If a different value of $p$ changes the execution, it may produce a different pair of activity values, but this is not a dependence of the inequality on the numerical size of $p$.

Therefore there cannot be a phenomenon in which the inequality holds solely for $p$ close to $0$ or $1$ and fails for every other value of $p$. The parameter $p$ affects which executions are likely, not the activity comparison for a fixed execution.

Hence the proposed behavior is impossible.

$$ \boxed{\text{No}} $$

This completes the proof.

∎