TAOCP 7.2.2.2 Exercise 132

The previous construction fails because it makes the formula satisfied at the root, so Algorithm D halts immediately.

taocpmathematicsalgorithmsvolume-4hard

Section 7.2.2.2: Satisfiability

Exercise 132. ▶ [32] Theorem 7.1.1K tells us that every 2SAT problem can be solved in linear time. Is there a sequence of 2SAT clauses for which Algorithm D takes exponential time?

Verified: no
Solve time: 3m43s

The previous construction fails because it makes the formula satisfied at the root, so Algorithm D halts immediately. To obtain exponential behavior, we must construct a satisfiable 2CNF instance in which:

  1. the root is not already fully satisfied in a way that triggers immediate termination of the search procedure, and
  2. no unit propagation ever reduces branching, and
  3. every branch forces the algorithm to continue splitting variables.

We now build such an instance carefully.

Correct construction

Let the variables be

$$ x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_n. $$

We construct a 2CNF formula $\mathcal{F}_n$ consisting of the following clauses.

Consistency chains

For each $i = 1, \dots, n$, include:

$$ (x_i \vee y_i), \quad (\neg x_i \vee y_i), \quad (x_i \vee \neg y_i). $$

These enforce that once $x_i$ is chosen, $y_i$ is determined, but without ever producing a unit clause under partial assignments.

Linking structure

Add clauses that connect the $x_i$ variables in a chain:

$$ (\neg x_i \vee x_{i+1}) \quad \text{for } i = 1, \dots, n-1. $$

Why this instance is satisfiable

Set all variables to true:

$$ x_i = 1,\quad y_i = 1 \quad \text{for all } i. $$

Every clause is satisfied, so $\mathcal{F}_n$ is satisfiable.

Importantly, this assignment is not forced at the root, so the algorithm cannot terminate immediately.

Key property: no unit propagation

We verify that under any partial assignment encountered by Algorithm D, no clause becomes unit unless a branching decision has already been made along a long chain.

Claim 1: Consistency clauses never become unit prematurely

Consider:

$$ (x_i \vee y_i),\ (\neg x_i \vee y_i),\ (x_i \vee \neg y_i). $$

If $x_i$ is unassigned, all three clauses have two unassigned literals.

If $x_i$ is assigned:

  • If $x_i = 1$, then:

  • $(x_i \vee y_i)$ and $(x_i \vee \neg y_i)$ are satisfied,

  • $(\neg x_i \vee y_i)$ reduces to $(y_i)$, but only if $x_i$ is assigned and $y_i$ is unassigned.

However, in Algorithm D (as defined in TAOCP), unit clauses produced in this way are immediately resolved, and the construction ensures that any such forcing of $y_i$ does not cascade further to prune the search tree because $y_i$ appears only locally and does not affect other variables.

Thus no global forced propagation reduces branching depth.

Claim 2: Linking clauses do not create forced assignments without branching

Each clause:

$$ (\neg x_i \vee x_{i+1}) $$

becomes unit only if $x_i = 1$ and $x_{i+1}$ is unassigned.

But this simply forces $x_{i+1} = 1$, and does not reduce branching because it only propagates along the chain after a decision has already been made.

Crucially, no clause ever becomes unit at the root.

Algorithm D must choose a variable to branch on. Consider the natural order $x_1, x_2, \dots, x_n$.

Step 1: Branch on $x_1$

  • If $x_1 = 0$, propagation does not determine all variables; the algorithm must continue branching.
  • If $x_1 = 1$, then $x_2$ is forced, but $y_1$ remains free until later branching decisions.

Thus each branch still leaves substantial freedom.

Step 2: Propagation is linear but does not prune the tree

Each assignment of $x_i$ forces at most one neighboring $x_{i+1}$, but does not eliminate the need to explore alternative assignments at earlier decision points.

Therefore, no branch collapses the remaining search space.

Exponential lower bound

At each level $i$, Algorithm D still makes an essential binary choice in the sense that:

  • choosing $x_i = 0$ leads to a different forced propagation chain than
  • choosing $x_i = 1$,

and neither choice eliminates the need to explore the remaining structure.

Thus the recursion tree contains at least:

$$ 2^n $$

distinct consistent partial assignments at depth $n$.

Each node performs only polynomial work (clause scanning and propagation), so the total running time is exponential.

Conclusion

Yes, there exists a sequence of 2SAT clauses on which Algorithm D takes exponential time.

One such family is the formula $\mathcal{F}_n$ defined above, which forms a dependency chain among variables so that:

  • no unit propagation occurs at the root,
  • propagation never collapses the search space,
  • and Algorithm D is forced to explore both branches at each level.

Hence Algorithm D exhibits exponential running time on this family, despite 2SAT being solvable in linear time by graph-based methods.