A 2-CNF formula with n variables and δn clauses can be compiled into an ordered binary decision diagram. When δ is small (few clauses per variable), the OBDD is polynomial-sized — the formula is simple enough to represent compactly. When δ is large (many clauses per variable), the OBDD is again polynomial-sized — the formula is constrained enough that most of its structure is redundant.

Between these regimes, when 1/2 < δ < 1, the OBDD blows up exponentially. The formula is neither simple enough to represent cheaply nor constrained enough to compress. The worst complexity lives in the middle.

This is a re-entrant phase transition. The system passes through three regimes — easy, hard, easy again — as a single parameter increases monotonically. The hard phase is not at the extreme of constraint but in the intermediate zone where the formula has enough structure to be complex but not enough to be redundant.

The thresholds are not arbitrary. δ = 1/2 coincides with the treewidth transition of random 2-CNF: below this density, the formula’s structure is tree-like and compressible. δ = 1 coincides with the satisfiability transition: above this density, most formulas are unsatisfiable, and their inconsistency compresses. The complexity peak lives in the window where the formula is satisfiable but no longer tree-structured — rich enough to encode hard structure, sparse enough that the structure isn’t forced.

The through-claim: difficulty is not a monotonic function of constraint. Adding constraints can make a problem easier, not because the constraints help you solve it, but because they eliminate the structural diversity that made it hard. The maximum complexity is not at maximum constraint. It’s at the point where the system has the most room to be complex.