TAOCP 7.2.2.2 Exercise 140

The earlier argument fails because ISTACK is not constrained by variables.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.2: Satisfiability

Exercise 140. [21] [21] The FORCE, BRANCH, BACKF, and BACKI arrays in Algorithm L will obviously never contain more than $n$ items each. Is there a fairly small upper bound on the maximum possible size of ISTACK?

Verified: no
Solve time: 2m26s

The earlier argument fails because ISTACK is not constrained by variables. It is constrained by implication events generated by clauses, and several distinct clauses can simultaneously contribute pending literals before any are processed.

We restart the analysis from the actual mechanism of Algorithm L.

Structure of ISTACK in Algorithm L

ISTACK is the stack (or list) of pending implied literals generated during unit propagation. A literal is inserted into ISTACK when some clause becomes unit under the current partial assignment and forces that literal to be true.

Thus every entry of ISTACK has the form

$$ x_i \quad \text{or} \quad \bar{x}_i, $$

and is generated by a specific clause whose remaining unassigned literal is uniquely determined at that moment.

Key invariant: one pending implication per clause

Fix a clause $C$. During propagation, $C$ can generate a forced literal only when all but one of its literals are falsified. At that moment:

  • $C$ contributes exactly one implied literal,
  • that literal is pushed onto ISTACK,
  • and $C$ becomes either satisfied or “resolved” once its implication is processed.

Crucially, Algorithm L ensures that:

  • a clause that has already produced a pending implication cannot produce another one until backtracking changes the assignment enough to “reset” the clause state,
  • during a single forward propagation phase, each clause contributes at most one unprocessed implication.

Therefore, at any moment, there is an injective mapping:

$$ \text{ISTACK entries} \longrightarrow \text{clauses that are currently unit and not yet processed}. $$

Bounding the number of simultaneous pending implications

Since each entry of ISTACK arises from a distinct clause, the size of ISTACK is bounded by the number of clauses.

Let $m$ be the number of clauses in the formula.

At any time during a single propagation phase:

  • each clause contributes at most one pending implication,
  • no clause can generate a second ISTACK entry before the first is processed,
  • hence no clause can be responsible for more than one element of ISTACK simultaneously.

Therefore,

$$ |\mathrm{ISTACK}| \le m. $$

Conclusion

A fairly small and natural upper bound on the maximum size of ISTACK in Algorithm L is the number of clauses:

$$ \boxed{|\mathrm{ISTACK}| \le m.} $$

This bound is independent of $n$, and it reflects the true source of growth in ISTACK: unit clauses generated by the clause set rather than variables.